recursive

Pages: 12
ocKiNOsIi (84)
could someone review my code I am working on the add/multiply portion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
#include <iostream>
#include <iomanip>
#include <algorithm> // for min, max
using namespace std;

// ===========ADD==================
int add2_fx(int a, int b) { // functional (for illustration only), PROVIDED
  return a+b;
}

int add2_loop(int a, int b) { // looping, PROVIDED
  int sum=a;
  if (b>0)
    for (int i=0; i<b; ++i) ++sum;
  else // b<=0
    for (int i=b; i<0; ++i) --sum;
  return sum;
}

// Rule: Do NOT use the *, /, +, =, *=, /=, +=, -=, ^, &, <<, >> operators.
// DO NOT USE bitwise operators like: (a & b) << 1; These are not part of the course.
// You MAY use: ++ and/or -- (as done in add2_loop)
// Constraints: No loops allowed; no static local or global variables.
int add2_recurse(int a, int b) { // recursive
    if (a==0 and b==0) return 0;
    if (a==0 and b==1) return 1;
    if (a==1 and b==0) return 1;
    if (a==1 and b==1) return 2;
    int solution{};

        
    return solution; // modify/replace this with your return value
}


// ===========MULTIPLY==================
int mult2_fx(int a, int b) { // functional (for illustration only), PROVIDED, DO NOT CHANGE
  return a*b;
}

int mult2_loop(int a, int b) { // looping, PROVIDED, DO NOT CHANGE
  int product=0;
  if (b>0)
    for (int i=0; i<b; ++i) product+=a;
  else // b<=0
    for (int i=b; i<0; ++i) product-=a;
  return product;
}

int mult2_recurse(int a, int b) { // recursive
  // Rule: you may NOT use the *, *=, / or /= operators.
  // You MAY use: +, -, +=, -= operators (as done in mult2_loop)
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here; modify...

    if (b==0){
        return 0;
    }
    return a + mult2_recurse (a,b-1);
}


// ===========SEARCH LOOP==================

int search_loop(int array[], int size, int target) { // looping, PROVIDED, DO NOT CHANGE
  for (int i=0; i<size; ++i)
    if (array[i]==target) {return i;}
  return -1;
}

// Constraints: No loops allowed; no static local or global variables.
// Your new code goes here; modify...
int search_recurse(int array[], int size, int target) { // recursive
    
  return 0; // modify / replace this with your return value;  is 0 until new code added.
}



// ===========MESSAGE LAYOUT==================
enum control_flow_t {functional, looping, recursive};
void show_test(int n, string s, control_flow_t control_flow) {
  // utility function to format test output
  // n: test number; s: "description"; control_flow: functional, looping or recursive
  static const string fx="functional", sl="looping", sr="recursive";
  int max_len=max(fx.size(), max(sl.size(), sr.size()));
  string msg;
  switch (control_flow) {
    case functional: msg=fx;     break;
    case looping:    msg=sl;     break;
    case recursive:  msg=sr;     break;
    default:         msg="??";   break;
  }
  char iorr=msg[0];
  msg=" ("+msg+"): ";
  cout<<"\n"<<n<<iorr<<") "<<s<<setw(max_len+5)<<left<<msg;
}

void infinite_recursion() {
  // try at your own risk! Error message can be interesting.
  infinite_recursion();
}

// This code may be helpful when developing your recursive functions.
void recurse(int times_to_call) {
  // a generalized recursion outline; has 5 locations to do work...
  cout << "recurse head... " << "("<<times_to_call<<") " <<endl; // ALWAYS
  if (times_to_call>1) { // decision to recursive call
    cout << "recurse before call... " << "("<<times_to_call<<") " <<endl;
    recurse(times_to_call-1); // work (problem simplification) can be done inside the parameter list!
    cout << "recurse after call... " << "("<<times_to_call<<") " <<endl;
  } else {
    cout << "recurse else option... " << "("<<times_to_call<<") " <<endl;
  }
  cout << "recurse ...tail " << "("<<times_to_call<<") " <<endl; // ALWAYS
}


int main () {

  // ----- DO NOT CHANGE ANY CODE BELOW in main()
  
  cout<<"start...\n";
  show_test(4, "add2", functional);
  cout<<add2_fx( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_fx(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_fx(20, -9); cout<<" ";  // correct:  11
  cout<<add2_fx(-7, -5); cout<<" ";  // correct: -12
  show_test(4, "add2", looping);
  cout<<add2_loop( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_loop(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_loop(20, -9); cout<<" ";  // correct:  11
  cout<<add2_loop(-7, -5); cout<<" ";  // correct: -12
    
  show_test(4, "add2", recursive);
  cout<<add2_recurse( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_recurse(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_recurse(20, -9); cout<<" ";  // correct:  11
  cout<<add2_recurse(-7, -5); cout<<" ";  // correct: -12
  cout<<endl;

  show_test(5, "mult2", functional);
  cout<<mult2_fx( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_fx( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_fx(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_fx(-4, -100); cout<<" ";  // correct:  400
  show_test(5, "mult2", looping);
  cout<<mult2_loop( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_loop( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_loop(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_loop(-4, -100); cout<<" ";  // correct:  400
  show_test(5, "mult2", recursive);
  cout<<mult2_recurse( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_recurse( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_recurse(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_recurse(-4, -100); cout<<" ";  // correct:  400
  cout<<endl;

  int primes[] {211, 307, 401, 503, 601, 701, 809, 907, 1009, 1103}; // some numbers to search for
  int size_primes=sizeof(primes)/sizeof(primes[0]);  // get #elements in array
  
  show_test(6, "search", looping);
  cout<<search_loop(primes, size_primes, 211)<<", ";
  cout<<search_loop(primes, size_primes, 401)<<", ";
  cout<<search_loop(primes, size_primes, 907)<<", ";
  cout<<search_loop(primes, size_primes, 1103);
    
   
  show_test(6, "search", recursive);
  cout<<search_recurse(primes, size_primes, 211)<<", ";
  cout<<search_recurse(primes, size_primes, 401)<<", ";
  cout<<search_recurse(primes, size_primes, 907)<<", ";
  cout<<search_recurse(primes, size_primes, 1103)<<endl;
  
  return 0;
} // end of main
Last edited on
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
#include <iostream>
#include <cassert>

int add( int a, int b ) {

    if( b == 0 ) return a ; // a+0 == a

    // add 1s recursively if b is positive, subtract 1s recursively if b is negative
    else return b>0 ?  add( a, b-1 ) + 1 : add( a, b+1 ) - 1 ;
}

int mul( int a, int b ) {

    if( b == 0 ) return 0 ; // a*0 == 0

    // add 'a's recursively if b is positive, subtract 'a's recursively if b is negative
    else return b>0 ?  mul( a, b-1 ) + a : mul( a, b+1 ) - a ;
}

int main() {

    for( int a = -9 ; a < 10 ; ++a ) for( int b = -9 ; b < 10 ; ++b ) {

        assert( add(a,b) == (a+b) ) ; // sanity check
        assert( mul(a,b) == (a*b) ) ; // sanity check
        std::cout << a << " + " << b << " == " << add(a,b) << "  (" << a+b << ")\n"
                  << a << " * " << b << " == " << mul(a,b) << "  (" << a*b << ")\n" ;
    }
}

http://coliru.stacked-crooked.com/a/d95bf3fb8b42ddf6
ocKiNOsIi (84)
is there actually a way to do it without the *, *=, / or /= operators?

Rule: you may NOT use the *, *=, / or /= operators.
MikeyBoy (5631)
is there actually a way to do it without the *, *=, / or /= operators?


Um, that's exactly what JLBorges has just given you!
jonnin (11437)
he only used them to show it works in main, to self-test against the built in operation.
lastchance (6980)
ocKiNOsIi wrote:
is there actually a way to do it without the *, *=, / or /= operators?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <iostream>

int op( int a, int b, int finish, int increment )
{
    if ( b == 0 ) return finish ;
    else return b > 0 ?  op( a, b - 1, finish, increment ) + increment : op( a, b + 1, finish, increment ) - increment ;
}

int main() {

    for( int a = -9 ; a < 10 ; ++a ) for( int b = -9 ; b < 10 ; ++b )
    {
        std::cout << a << " + " << b << " = " << op(a,b,a,1) << "  (" << std::plus<int>()(a,b) << ")\n"
                  << a << " * " << b << " = " << op(a,b,0,a) << "  (" << std::multiplies<int>()(a,b) << ")\n" ;
    }
}
Last edited on
mbozzi (3932)
A function is called tail-recursive if the last thing it does is call itself. A tail-recursive function is also strictly tail-recursive if the arguments to the recursive call are the parameters to the function.

This is useful because strictly tail-recursive functions can be made iterative by replacing the recursion with a jump to the top.

Here mult2_recurse_impl is strictly tail-recursive:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
int mult2_recurse_impl(int a, int b, int product)
{
  if (a == 0) return product; 
  if (a < 0) { ++a; product -= b; }
  if (a > 0) { --a; product += b; }
 
  return mult2_recurse_impl(a, b, product);
}

int mult2_recurse(int a, int b)
{
  return mult2_recurse_impl(a, b, 0);
}


It's equivalent to
1
2
3
4
5
6
7
8
9
 
int mult2_recurse_impl(int a, int b, int product)
{
top: 
  if (a == 0) return product; 
  if (a < 0) { a += 1; product -= b; }
  if (a > 0) { a -= 1; product += b; }
 
  goto top;
}


It's also true that every recursive function can be written iteratively.

I'm telling you this because it suggests a strategy you may find occasionally helpful.
The idea is, you can look for an iterative solution first, then convert it into a recursive function.

So for example with add2 one could write this iterative solution:
1
2
3
4
5
6
7
 
int add(int a, int b)
{
  while (a > 0) { --a; ++b; }
  while (a < 0) { ++a; --b; }
  
  return b;
}


Then convert it into this strictly tail-recursive function:
1
2
3
4
5
6
7
 
int add2_recurse(int a, int b)
{
  if(a > 0) { --a; ++b; return add2_recurse(a, b); }
  if(a < 0) { ++a; --b; return add2_recurse(a, b); }
  
  return b;
}


This is equivalent to
1
2
3
4
5
6
7
8
 
int add(int a, int b)
{
top:
  if(a > 0) { --a; ++b; goto top; }
  if(a < 0) { ++a; --b; goto top; }
  
  return b;
}
Last edited on
jonnin (11437)
Its hard to describe, but I prefer iteration unless the recursion is using the call stack as part of the problem solving (saving creating a data structure or variables or something to store that info).
ocKiNOsIi (84)
thank you all for those explanations

can anyone review my code and let me know if there is anything I should change?
everything works..just finishing up and working on recursive multiplication

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
#include <iostream>
#include <iomanip>
#include <algorithm> // for min, max
using namespace std;
// ===========ADD==================
int add2_fx(int a, int b) { // functional (for illustration only), PROVIDED, DO NOT CHANGE
  return a+b;
}

int add2_loop(int a, int b) { // looping, PROVIDED, DO NOT CHANGE
  int sum=a;
  if (b>0)
    for (int i=0; i<b; ++i) ++sum;
  else // b<=0
    for (int i=b; i<0; ++i) --sum;
  return sum;
}

// Rule: Do NOT use the *, /, +, =, *=, /=, +=, -=, ^, &, <<, >> operators.
// DO NOT USE bitwise operators like: (a & b) << 1; These are not part of the course.
// You MAY use: ++ and/or -- (as done in add2_loop)
// Constraints: No loops allowed; no static local or global variables.
int add2_recurse(int a, int b) { // recursive
top:
    if(a > 0) { --a; ++b; goto top; }
    if(a < 0) { ++a; --b; goto top; }
    return b;
}

// ===========MULTIPLY==================
int mult2_fx(int a, int b) { // functional (for illustration only), PROVIDED, DO NOT CHANGE
  return a*b;
}

int mult2_loop(int a, int b) { // looping, PROVIDED, DO NOT CHANGE
  int product=0;
  if (b>0)
    for (int i=0; i<b; ++i) product+=a;
  else // b<=0
    for (int i=b; i<0; ++i) product-=a;
  return product;
}

int mult2_recurse(int a, int b) { // recursive
  // Rule: you may NOT use the *, *=, / or /= operators.
  // You MAY use: +, -, +=, -= operators (as done in mult2_loop)
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here; modify...
    
    
    
    
    return 0;
}

// ===========SEARCH LOOP==================

int search_loop(int array[], int size, int target) { // looping, PROVIDED, DO NOT CHANGE
  for (int i=0; i<size; ++i)
    if (array[i]==target) {return i;}
  return -1;
}

// Constraints: No loops allowed; no static local or global variables.
// Your new code goes here; modify...
int search_recurse(int array[], int size, int target) {// recursive
    size--;
    int rec;
    if (size >= 0){
        if (array[size] == target)
            return size;
        else
            rec = search_recurse(array, size, target);
    }
    else
        return -1;
    return rec;
}
    

// ===========MESSAGE LAYOUT==================
enum control_flow_t {functional, looping, recursive};
void show_test(int n, string s, control_flow_t control_flow) {
  // utility function to format test output
  // n: test number; s: "description"; control_flow: functional, looping or recursive
  static const string fx="functional", sl="looping", sr="recursive";
  int max_len=max(fx.size(), max(sl.size(), sr.size()));
  string msg;
  switch (control_flow) {
    case functional: msg=fx;     break;
    case looping:    msg=sl;     break;
    case recursive:  msg=sr;     break;
    default:         msg="??";   break;
  }
  char iorr=msg[0];
  msg=" ("+msg+"): ";
  cout<<"\n"<<n<<iorr<<") "<<s<<setw(max_len+5)<<left<<msg;
}

void infinite_recursion() {
  // try at your own risk! Error message can be interesting.
  infinite_recursion();
}

// This code may be helpful when developing your recursive functions.
void recurse(int times_to_call) {
  // a generalized recursion outline; has 5 locations to do work...
  cout << "recurse head... " << "("<<times_to_call<<") " <<endl; // ALWAYS
  if (times_to_call>1) { // decision to recursive call
    cout << "recurse before call... " << "("<<times_to_call<<") " <<endl;
    recurse(times_to_call-1); // work (problem simplification) can be done inside the parameter list!
    cout << "recurse after call... " << "("<<times_to_call<<") " <<endl;
  } else {
    cout << "recurse else option... " << "("<<times_to_call<<") " <<endl;
  }
  cout << "recurse ...tail " << "("<<times_to_call<<") " <<endl; // ALWAYS
}


int main () {
  // ----- DO NOT CHANGE ANY CODE BELOW in main(). CALLS FUNCTIONS ABOVE FOR TESTING -----
  
  cout<<"start...\n";
  show_test(4, "add2", functional);
  cout<<add2_fx( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_fx(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_fx(20, -9); cout<<" ";  // correct:  11
  cout<<add2_fx(-7, -5); cout<<" ";  // correct: -12
  show_test(4, "add2", looping);
  cout<<add2_loop( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_loop(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_loop(20, -9); cout<<" ";  // correct:  11
  cout<<add2_loop(-7, -5); cout<<" ";  // correct: -12
    
  show_test(4, "add2", recursive);
  cout<<add2_recurse( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_recurse(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_recurse(20, -9); cout<<" ";  // correct:  11
  cout<<add2_recurse(-7, -5); cout<<" ";  // correct: -12
  cout<<endl;

  show_test(5, "mult2", functional);
  cout<<mult2_fx( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_fx( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_fx(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_fx(-4, -100); cout<<" ";  // correct:  400
  show_test(5, "mult2", looping);
  cout<<mult2_loop( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_loop( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_loop(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_loop(-4, -100); cout<<" ";  // correct:  400
  show_test(5, "mult2", recursive);
  cout<<mult2_recurse( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_recurse( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_recurse(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_recurse(-4, -100); cout<<" ";  // correct:  400
  cout<<endl;

  int primes[] {211, 307, 401, 503, 601, 701, 809, 907, 1009, 1103}; // some numbers to search for
  int size_primes=sizeof(primes)/sizeof(primes[0]);  // get #elements in array
  
  show_test(6, "search", looping);
  cout<<search_loop(primes, size_primes, 211)<<", ";
  cout<<search_loop(primes, size_primes, 401)<<", ";
  cout<<search_loop(primes, size_primes, 907)<<", ";
  cout<<search_loop(primes, size_primes, 1103);
    
   
  show_test(6, "search", recursive);
  cout<<search_recurse(primes, size_primes, 211)<<", ";
  cout<<search_recurse(primes, size_primes, 401)<<", ";
  cout<<search_recurse(primes, size_primes, 907)<<", ";
  cout<<search_recurse(primes, size_primes, 1103)<<endl;
  
  // infinite_recursion();  // uncomment to experience infinite recursion (crash, error message)
  cout<<"\n...end\n";
    
  return 0;
}
jonnin (11437)
line 23 block is a total fail.
1) goto is a loop. that is not allowed.
2) it claims recursion. it has none.


66 search can be polished a little
something like
if size is -1 return -1
if array[size] == target return size
return recurse(blah blah size -1 blah )
I don't think you need that rec variable or the size-- etc clutter.
No harm, just a little rough :)

Last edited on
ocKiNOsIi (84)
pretty sure my n to 1 recursion is incorrect since my output is
2r) show_n_to_1 (recursive): 1 0 -1 -2 -3 -4 -5


shouldn't it be the other way? what can I do to fix this?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
#include <iostream>
#include <iomanip>
#include <algorithm> // for min, max
using namespace std;

// ===========1 TO n==================
void show_1_to_n_loop(int n) { // 1 to n, looping, PROVIDED, DO NOT CHANGE
  for (int i=1; i<=n; ++i) cout<<i<<" ";
}

// Constraints: No loops allowed; no static local or global variables.
void show_1_to_n_recurse(int n) { // 1 to n, recursive
    if (n>=1)// won't recurse any further once n gets to 0, no negative numbers
    {
        show_1_to_n_recurse(n-1);
        cout << n << " ";
    }
}

// ===========n TO 1==================
void show_n_to_1_loop(int n) { // looping, PROVIDED, DO NOT CHANGE
    for (int i=n; i>=1; --i) cout<<i<<" ";
}

// Constraints: No loops allowed; no static local or global variables.
void show_n_to_1_recurse(int n) { // recursive
    if (n<=1)
    {
        show_n_to_1_recurse(n+1);
        cout <<n<<" ";
    }
}
 

// ===========ADD==================
int add2_fx(int a, int b) { // functional (for illustration only), PROVIDED, DO NOT CHANGE
  return a+b;
}

int add2_loop(int a, int b) { // looping, PROVIDED, DO NOT CHANGE
  int sum=a;
  if (b>0)
    for (int i=0; i<b; ++i) ++sum;
  else // b<=0
    for (int i=b; i<0; ++i) --sum;
  return sum;
}

// Rule: Do NOT use the *, /, +, =, *=, /=, +=, -=, ^, &, <<, >> operators.
// DO NOT USE bitwise operators like: (a & b) << 1; These are not part of the course.
// You MAY use: ++ and/or -- (as done in add2_loop)
// Constraints: No loops allowed; no static local or global variables.
int add2_recurse(int a, int b) { // recursive
    if(a > 0) { --a; ++b; return add2_recurse(a, b); }
    if(a < 0) { ++a; --b; return add2_recurse(a, b); }
    
    return b;
  //  return 0;
}

// ===========MULTIPLY==================
int mult2_fx(int a, int b) { // functional (for illustration only), PROVIDED, DO NOT CHANGE
  return a*b;
}

int mult2_loop(int a, int b) { // looping, PROVIDED, DO NOT CHANGE
  int product=0;
  if (b>0)
    for (int i=0; i<b; ++i) product+=a;
  else // b<=0
    for (int i=b; i<0; ++i) product-=a;
  return product;
}

int mult2_recurse(int a, int b) { // recursive
  // Rule: you may NOT use the *, *=, / or /= operators.
  // You MAY use: +, -, +=, -= operators (as done in mult2_loop)
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here; modify...
    
    return 0;
}


// ===========MESSAGE LAYOUT==================
enum control_flow_t {functional, looping, recursive};
void show_test(int n, string s, control_flow_t control_flow) {
  // utility function to format test output
  // n: test number; s: "description"; control_flow: functional, looping or recursive
  static const string fx="functional", sl="looping", sr="recursive";
  int max_len=max(fx.size(), max(sl.size(), sr.size()));
  string msg;
  switch (control_flow) {
    case functional: msg=fx;     break;
    case looping:    msg=sl;     break;
    case recursive:  msg=sr;     break;
    default:         msg="??";   break;
  }
  char iorr=msg[0];
  msg=" ("+msg+"): ";
  cout<<"\n"<<n<<iorr<<") "<<s<<setw(max_len+5)<<left<<msg;
}


int main () {
  const string FIRSTNAME{"John"}; // modif y / change this to your first name
  const string LASTNAME{"Doe"};   // modif y / change this to your last name
  
  // ----- DO NOT CHANGE ANY CODE BELOW in main(). CODE BELOW CALLS FUNCTIONS ABOVE FOR TESTING -----
  
  cout<<"start...\n";
  
  show_test(1, "show_1_to_n", looping);    show_1_to_n_loop(15);
  show_test(1, "show_1_to_n", looping);    show_1_to_n_loop(-9);    // handle unexpected values
  show_test(1, "show_1_to_n", recursive);  show_1_to_n_recurse(15);
  show_test(1, "show_1_to_n", recursive);  show_1_to_n_recurse(-9); // avoid runaway recursion
  cout<<endl;
  
  show_test(2, "show_n_to_1", looping);    show_n_to_1_loop(11);
  show_test(2, "show_n_to_1", looping);    show_n_to_1_loop(-5);    // handle unexpected values
  show_test(2, "show_n_to_1", recursive);  show_n_to_1_recurse(11);
  show_test(2, "show_n_to_1", recursive);  show_n_to_1_recurse(-5); // avoid runaway recursion
  cout<<endl;


  show_test(4, "add2", functional);
  cout<<add2_fx( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_fx(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_fx(20, -9); cout<<" ";  // correct:  11
  cout<<add2_fx(-7, -5); cout<<" ";  // correct: -12
  show_test(4, "add2", looping);
  cout<<add2_loop( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_loop(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_loop(20, -9); cout<<" ";  // correct:  11
  cout<<add2_loop(-7, -5); cout<<" ";  // correct: -12
    
  show_test(4, "add2", recursive);
  cout<<add2_recurse( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_recurse(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_recurse(20, -9); cout<<" ";  // correct:  11
  cout<<add2_recurse(-7, -5); cout<<" ";  // correct: -12
  cout<<endl;

  show_test(5, "mult2", functional);
  cout<<mult2_fx( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_fx( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_fx(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_fx(-4, -100); cout<<" ";  // correct:  400
  show_test(5, "mult2", looping);
  cout<<mult2_loop( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_loop( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_loop(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_loop(-4, -100); cout<<" ";  // correct:  400
  show_test(5, "mult2", recursive);
  cout<<mult2_recurse( 50,   2); cout<<" ";  // correct:  100
  cout<<mult2_recurse( 5,  -40); cout<<" ";  // correct: -200
  cout<<mult2_recurse(-100,  3); cout<<" ";  // correct: -300
  cout<<mult2_recurse(-4, -100); cout<<" ";  // correct:  400
  cout<<endl;

 
  
  // infinite_recursion();  // uncomment to experience infinite recursion (crash, error message)
  cout<<"\n...end\n";
    
  return 0;
} // end of main
seeplus (6591)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>

void show_n_to_1_recurse(int n) { // recursive
	if (n > 0) {
		std::cout << n << ' ';
		show_n_to_1_recurse(n - 1);
	}
}

void show_1_to_n_recurse(int n) { // 1 to n, recursive
	if (n > 0) {
		show_1_to_n_recurse(n - 1);
		std::cout << n << ' ';
	}
}

int main()
{
	show_n_to_1_recurse(7);
	std::cout << '\n';
	show_1_to_n_recurse(7);
	std::cout << '\n';
}



7 6 5 4 3 2 1
1 2 3 4 5 6 7


The code for 1-n and n-1 is basically the same except for the order of the cout/recursive function call.
Last edited on
ocKiNOsIi (84)
ahh I see I fixed it now

for multiplication how do I continue from here?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int mult2_recurse(int a, int b ) { // recursive
  // Rule: you may NOT use the *, *=, / or /= operators.
  // You MAY use: +, -, +=, -= operators (as done in mult2_loop)
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here; modify...
    
    if( a ==0 || b == 0)
    {
       return 0;
    }
    if (b==1)
    {
        return a;
    }
    else
    {
        return ??? mult2_recurse(??? );
    }
}
Last edited on
Ganado (6810)
a * b = a + a + a + a ... (b times). You already have your terminating condition of b == 1, so you need to add a and decrement b.
seeplus (6591)
From JLBorges post above:

1
2
3
4
5
6
7
 
int mul( int a, int b ) {

    if ( b == 0 ) return 0 ; // a*0 == 0

    // add 'a's recursively if b is positive, subtract 'a's recursively if b is negative
    return b > 0 ?  mul( a, b - 1 ) + a : mul( a, b + 1 ) - a ;
}


Just replace the function name.
Topic archived. No new replies allowed.
Pages: 12