### recursive

Pages: 12
could someone review my code I am working on the add/multiply portion
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176`` ``````#include #include #include // 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> 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; i1) { // decision to recursive call cout << "recurse before call... " << "("<
Last edited on
 ``1234567891011121314151617181920212223242526272829`` ``````#include #include 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
is there actually a way to do it without the *, *=, / or /= operators?

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

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

 ``12345678910111213141516`` ``````#include 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()(a,b) << ")\n" << a << " * " << b << " = " << op(a,b,0,a) << " (" << std::multiplies()(a,b) << ")\n" ; } }``````
Last edited on
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:
 ``12345678910111213`` ``````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
 ``123456789`` ``````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:
 ``1234567`` ``````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:
 ``1234567`` ``````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
 ``12345678`` ``````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
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).
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

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179`` ``````#include #include #include // 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> 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= 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"<1) { // decision to recursive call cout << "recurse before call... " << "("<
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
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?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167`` ``````#include #include #include // 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<=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<0) for (int i=0; i> 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
 ``1234567891011121314151617181920212223`` ``````#include 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
ahh I see I fixed it now

for multiplication how do I continue from here?
 ``12345678910111213141516171819`` ``````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
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.
From JLBorges post above:

 ``1234567`` ``````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