dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 15 of 15

Thread: Yet another question about recursion

  1. #1
    Join Date
    Feb 2006
    Posts
    127

    Yet another question about recursion

    Hello. I thought I'd grasped how recursion works but it appears as though that is not the case.
    I have no earthly idea how to computer the output of the following function on paper. I would really appreciate if someone could help me to do just that.

    Here is the code:

    Code:
    #include <iostream>
    
    using namespace std;
    
    int func( int n)
    {
     if(n==0)
      return 1;
     if(n==1)
      return 2;
     else
      return (func(n-2)*(func(n-1)));
    
    }
    
    int main()
    {
    
    cout << func(5) << endl;
    
    }
    Thank you.

  2. #2
    Join Date
    Oct 2006
    Location
    Sweden
    Posts
    3,654

    Re: Yet another question about recursion

    Do it kind of the same way a macro works but do it iteratively
    Code:
    cout << func(5) << endl; since n <> 0 and n <> 1 it translates to
    cout << func(5-2)*func(5-1) << endl;
    which translates to
    and so on
    Debugging is twice as hard as writing the code in the first place.
    Therefore, if you write the code as cleverly as possible, you are, by
    definition, not smart enough to debug it.
    - Brian W. Kernighan

    To enhance your chance's of getting an answer be sure to read
    http://www.codeguru.com/forum/announ...nouncementid=6
    and http://www.codeguru.com/forum/showthread.php?t=366302 before posting

    Refresh your memory on formatting tags here
    http://www.codeguru.com/forum/misc.php?do=bbcode

    Get your free MS compiler here
    https://visualstudio.microsoft.com/vs

  3. #3
    Join Date
    Aug 2007
    Posts
    858

    Re: Yet another question about recursion

    I'm having a hell of a mathematical brain fart at the moment, but the long way to do it would simply be to substitute in until you're left with a numerical answer.

    func(5) = func(3)*func(4) = 2*func(2)*func(2)*func(3) = 2*2*2*2*func(2) = 16*2 = 32

  4. #4
    Join Date
    Feb 2006
    Posts
    127

    Re: Yet another question about recursion

    Well, thanks..not that I would get it but it helps.

    I really dont get it... :-(
    Last edited by slewrate; April 13th, 2009 at 05:06 PM.

  5. #5
    Join Date
    Aug 2007
    Posts
    858

    Re: Yet another question about recursion

    Recursion is nothing more than a function calling itself. Consider a more simple example.

    Code:
    #include <iostream>
    
    void Printer(int i)
    {
      std::cout << "i = " << i << std::endl;
    
      if (i > 0)
      {
        Printer(i - 1);
      }
    }
    
    int main( )
    {
      Printer(10);
    
      return 0;
    }
    If you don't understand the code itself, step through it line by line in your debugger and watch what it does.

  6. #6
    Join Date
    Feb 2006
    Posts
    127

    Re: Yet another question about recursion

    I do understand these basic recursion examples.

    I just fail to understand what happens...step by step in that example above..I think it is because it has 2 function calls.

  7. #7
    Join Date
    Jun 2006
    Posts
    437

    Re: Yet another question about recursion

    Hi all.

    Where is the problem? Recursive functions simply call themselves; infact, in the example you showed func() calls itself (two time).
    You can easily (more or less) tracking the execution of function on paper.
    So, func(5):
    Call 0
    5 is equal to 0? No
    5 is equal to 1? No
    Then call 1 func(5-2) -> func(3) and call 2 func(5-1) -> func(4)
    Call 1
    3 is equal to 0? No
    3 is equal to 1? No
    Then call 3 func(3-2) -> func(1) and call 4 func(3-1) -> func(2)
    Call 3
    1 is equal to 0? No
    1 is equal to 1? Yes!!! so Call 3 returns 2 and you can substitute Call 3 with 2 in Call 1, and later calculate 2 * the result of func(2)
    And so on...

    You have to be patient.

    Well, probably this function isn't the best example to introduce recursion, because there're two recursive calls, as you pointed out. Moreover, it doesn't implement a "real" function.

    Maybe understanding recursion is simpliest starting with a classical example, the factorial function.
    You know that
    5! = 5*4*3*2*1
    or
    5! = 5 * 4!
    Because 1! = 1, you can write
    n! = if n = 1 then 1, else n*(n-1)!
    Starting with the last statement it's very simple to write a recursive function to calculate factorial

    Code:
    int Factorial(int n)  // It works if n > 0
    {
    	if( n == 1 )
    		return 1;
    	else
    		return n * Factorial(n - 1);
    }
    Let see how it works
    Factorial(1)
    Call 1 returns 1, OK
    Factorial(2)
    Call 1 means 2 * Factorial(1) (call 2)
    Call 2 returns 1, so in Call 1 there's 2 * 1 = 2, OK
    Factorial(3)
    Call 1 means 3 * Factorial(2) (call 2)
    Call 2 means 2 * Factorial(1) (call 3)
    Call 3 returns 1
    Call 2 means 2 * 1 = 2
    Call 1 means 3 * 2 = 6, OK
    Factorial(4)
    Try yourself...

    I hope this will help you.
    Last edited by davide++; April 14th, 2009 at 12:18 PM.

  8. #8
    Join Date
    Feb 2006
    Posts
    127

    Re: Yet another question about recursion

    Thanks, I am trying to wrap my head around it. Thanks for your help.

  9. #9
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Yet another question about recursion

    Draw a tree structure on paper. Should make it easier. For instance, start with
    Code:
          func(5)
          |    |
    func(3)    func(4)
    and proceed down from there. The final result is the product of all leaves of the tree.

    The thing is, though, recursion isn't supposed to be easy to understand completely. The whole point is that it allows you to concisely express concepts and relationships which would be far more difficult to calculate without using recursion. When traversing a binary tree, you don't want or need to know what the entire tree looks like----you can make decisions based purely on the value of the current node and how many children it has, for instance.
    Last edited by Lindley; April 16th, 2009 at 05:54 PM.

  10. #10
    Join Date
    Feb 2006
    Posts
    127

    Re: Yet another question about recursion

    Thanks for your answer Lindley. I was trying to do it the way you suggested. For some reason I am unable to come up with the same result as my program, which means I do something wrong.
    The final output of the program is 32. I guess my question is why ?

  11. #11
    Join Date
    Jun 2008
    Posts
    12

    Re: Yet another question about recursion

    Yes, these are very confusing. Maybe a different approach may help you. I think of recursion as solving those fractions in fractions. For example, let's say you have:
    f(x) = 1+2/(3+4/(5+etc until x)) (I suggest you draw the fractions with paper/pencil)
    In order to solve the highest layer, you must sum the denominator under 2. But, to solve the denominator of 2, you have to first solve the one under 6. And so on until you get to the last one.
    The same goes for recursive functions. (You are recursively solving this problem btw)
    In order to find 6! you must find 5! and to find 5! you must find 4! and so on.
    Once you find the solution to the lowermost layer (1! for example), you can go back up the chain to reach your solution.

    Hope this helps.
    Last edited by std; April 16th, 2009 at 09:21 PM.
    You know you're a C++ Programmer when the first thought to come to mind when seeing 'std' is the namespace std, and the second thought is namespaces in general, the third thought being how to improve that program you're working on, and finally the fourth thought being sexually transmitted diseases.

  12. #12
    Join Date
    Feb 2006
    Posts
    127

    Re: Yet another question about recursion

    I tried to start with a smaller number. Starting for example with 2.

    2
    / \ result is 2
    1 2

    3
    / \ result =4
    2 2

    4
    / \ result =8
    2 * 3 =4
    / \ +
    2 2 =4

    this all makes sense but

    5 result = 32
    / \
    3 * 4 = 12
    / \ / \
    2 2 2 3 = 20
    / \
    2 2 <- wouldn't i have to add this node ?????

    I guess to simplify my problem...at what is the rule for me to stop adding nodes to the tree ??

    I am sorry for being a bit difficult to deal with....I just want to understand this problem.
    Last edited by slewrate; April 16th, 2009 at 09:43 PM.

  13. #13
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Yet another question about recursion

    Quote Originally Posted by slewrate View Post
    I guess to simplify my problem...at what is the rule for me to stop adding nodes to the tree ??
    The base case is right there in the function: You stop when you pass 0 or 1. However, if you've already computed the function's result for some smaller values, there's really need to go past even *those*. For instance, consider:

    Code:
             5   result = 32
            / \
           3   4
    You've already computed above that f(3) = 4 and f(4) = 8. Therefore, your 5-tree can stop right here-----there's no need to go any lower, because you can simply observe that 4*8 = 32. Similarly, you can then conclude that f(6) = f(4)*f(5) = 8 * 32 = 256 and so on.

    This sort of approach has a name, actually. It's called dynamic programming, and it's a lot more efficient than actually expanding the recursion all the way out. Don't worry about that for now, but I'm sure you'll hear the term eventually.
    Last edited by Lindley; April 16th, 2009 at 11:59 PM.

  14. #14
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,559

    Re: Yet another question about recursion

    Better yet, run the code in the debugger step by step. That'll let you see exactly what it's doing and what values the variables contain.

  15. #15
    Join Date
    Feb 2006
    Posts
    127

    Resolved Re: Yet another question about recursion

    Quote Originally Posted by Lindley View Post
    The base case is right there in the function: You stop when you pass 0 or 1. However, if you've already computed the function's result for some smaller values, there's really need to go past even *those*. For instance, consider:

    Code:
             5   result = 32
            / \
           3   4
    You've already computed above that f(3) = 4 and f(4) = 8. Therefore, your 5-tree can stop right here-----there's no need to go any lower, because you can simply observe that 4*8 = 32. Similarly, you can then conclude that f(6) = f(4)*f(5) = 8 * 32 = 256 and so on.

    This sort of approach has a name, actually. It's called dynamic programming, and it's a lot more efficient than actually expanding the recursion all the way out. Don't worry about that for now, but I'm sure you'll hear the term eventually.

    I can not thank you enough, Lindley. That helps !!!!!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)