Re: [Dev-C++] recursion help

[Chris I. <chr...@li...>]

Richard Gelling wrote:

> Hi,
>
> I am working my way through Sams Teach yourself c++ in 21 days and am 
> having a bit fof difficulty with recursion, could someone explain to 
> me how the following oiece of code works:
>
> #ifdef HAVE_CONFIG_H
> #include <config.h>
> #endif
>
> #include <iostream>
> #include <cstdlib>
>
> using namespace std;
>
> int toPowerOf( int , int );
> int main(int argc, char *argv[])
> {
>    int powerOf, number, result;
>    cout << "\nEnter the number: ";
>    cin >> number;
>    cout << "\nEnter the exponential: ";
>    cin >> powerOf;
>      result = toPowerOf( number, powerOf );
>      cout << "\nThe result of " << number << "  to the power of " << 
> powerOf << " is " << result << endl;
>      return 0;
> }
> int toPowerOf( int number, int powerOf )
> {
>     if ( powerOf == 1 )
>        return number;
>     else
>    {
>        cout << "number is: " << number << " and the power of is " << 
> powerOf << endl;
>        return ( number  * toPowerOf( number, powerOf - 1 ));
>    }
>   }
>
> If someone could explain how the recusion side workd I would be 
> gratefull, as I don't seem to be getting anywhere.
>
> Thanks a lot
> Richard G.
>
>
Note: Expand this window till you have the columns all lined up in my 
explanation below.

Well I'm by no means a master of recursion but I believe this example 
works like this...... someone correct me if I'm wrong.  Recursion uses 
the a stack for each call to the recursive function.  So the first call 
is made, lets say with the values (2,3).  Then the first call calls 
itself but with the values (2,2) now, pushing its call onto the stack 
(like a stack of plates). Then the second call calls itself again with 
the values (2,1).... now in the third call..... powerOf == 1, so this 
stops the recursive calls and the returned value is the 2......that call 
is popped off the stack and that returned 2 it multiplied by the 2 in 
the second call, then the returned value is (2*2), the second call is 
now popped off the stack and that returned (2*2) is multiplied by the 
last 2 (which is the first call's 2)....... so then "result" is set to 8 
which is 2^3.

//push                    //push                     //push then pop'd   
               //pop                                           //pop
toPowerOf(2,3)    toPowerOf(2,2)      toPowerOf(2,1) //returns 2   
toPowerOf(2,2) //returns (2*2)   toPowerOf(2,3)
                             toPowerOf(2,3)      toPowerOf(2,2)      
              toPowerOf(2,3)
                                                            toPowerOf(2,3)

The last one returns 2*2*2

Hope that helps...... I find recursion difficult too :)