dev-cpp-users

[Dev-C++] recursion help

[Richard G. <use...@ya...>]

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.

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 :)

Re: [Dev-C++] recursion help

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

Looks like the formatting came out all screwy..... here's a screenshot 
of what it should look like

Later, Chris

Re: [Dev-C++] recursion help

[Richard G. <use...@ya...>]

Chris Irish wrote:

> 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 :)
>
>
> -------------------------------------------------------
> SF.Net email is sponsored by:
> Tame your development challenges with Apache's Geronimo App Server. 
> Download
> it for free - -and be entered to win a 42" plasma tv or your very own
> Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
Thanks for that everyone, that's made it clearer, I think I was 
suffering from a mental block,

Re: [Dev-C++] recursion help

[Robert A. <ral...@gm...>]

Recursion works by solving a simpler problem. In the case above you know
that if you raise any number to the 1st power then you get that number back=
,
Otherwise you can get the result by multipling the number by the number
raised to the initial power minus one.

So if I am going to raise 10 to the third power ie pow(10,3)

pow(10,3)=3D10*pow(10,2)
pow(10,2)=3D10*pow(10,1)
pow(10,1)=3D10

So... now backing up as each function returns you get
pow(10,3)=3D10*10*10



On 11/8/05, Richard Gelling <use...@ya...> 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 =3D 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 =3D=3D 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.
>
>
>
>
> -------------------------------------------------------
> SF.Net email is sponsored by:
> Tame your development challenges with Apache's Geronimo App Server.
> Download
> it for free - -and be entered to win a 42" plasma tv or your very own
> Sony(tm)PSP. Click here to play: http://sourceforge.net/geronimo.php
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

Re: [Dev-C++] recursion help

[Fernando L. <fer...@gm...>]

I looked it up in Stan Kelly-Bootle's "The Devil's DP Dictionary" and
I found this:

recursion: see recursion

Now serously, in programming recursion means that a function can call
itself. The power example is a good one, another classic one is to say
that

factorial(n) =3D n * factorial (n - 1)

This could go on endlessly if it were not for the fact that 0! =3D 1, so
a recursive factorial function would call itself until its argument
became 0, where it would return 1 and unwind the chain of calls.

A similar reasoning could be applied to analizing sentences, or
traversing the leaves of a binary tree.

Regards,

On 11/8/05, Robert Alatalo <ral...@gm...> wrote:
> Recursion works by solving a simpler problem.  In the case above you know
> that if you raise any number to the 1st power then you get that number ba=
ck,
>   Otherwise you can get the result by multipling the number by the number
> raised to the initial power minus one.
>
> So if I am going to raise 10 to the third power ie pow(10,3)
>
> pow(10,3)=3D10*pow(10,2)
> pow(10,2)=3D10*pow(10,1)
> pow(10,1)=3D10
>
> So... now backing up as each function returns you get
> pow(10,3)=3D10*10*10
>
>
>
>
> On 11/8/05, Richard Gelling <use...@ya...> 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 =3D 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 =3D=3D 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.
> >
> >
> >
> >
> > -------------------------------------------------------
> > SF.Net email is sponsored by:
> > Tame your development challenges with Apache's Geronimo App Server.
> Download
> > it for free - -and be entered to win a 42" plasma tv or your very own
> > Sony(tm)PSP.  Click here to play:
> http://sourceforge.net/geronimo.php
> > _______________________________________________
> > Dev-cpp-users mailing list
> > Dev...@li...
> > TO UNSUBSCRIBE:
> http://www23.brinkster.com/noicys/devcpp/ub.htm
> >
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
> >
>
>


--
Fernando Lichtschein
li...@fi...