
April 13th, 2009, 03:35 PM
#1
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(n2)*(func(n1)));
}
int main()
{
cout << func(5) << endl;
}
Thank you.

April 13th, 2009, 03:53 PM
#2
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(52)*func(51) << endl;
which translates to
and so on

April 13th, 2009, 03:59 PM
#3
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

April 13th, 2009, 04:31 PM
#4
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.

April 13th, 2009, 10:47 PM
#5
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.

April 14th, 2009, 10:22 AM
#6
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.

April 14th, 2009, 11:59 AM
#7
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(52) > func(3) and call 2 func(51) > func(4)
Call 1
3 is equal to 0? No
3 is equal to 1? No
Then call 3 func(32) > func(1) and call 4 func(31) > 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*(n1)!
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.

April 16th, 2009, 04:58 PM
#8
Re: Yet another question about recursion
Thanks, I am trying to wrap my head around it. Thanks for your help.

April 16th, 2009, 05:51 PM
#9
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 likeyou 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.

April 16th, 2009, 08:42 PM
#10
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 ?

April 16th, 2009, 09:10 PM
#11
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.

April 16th, 2009, 09:41 PM
#12
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.

April 16th, 2009, 11:56 PM
#13
Re: Yet another question about recursion
Originally Posted by slewrate
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 5tree can stop right herethere'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.

April 17th, 2009, 07:10 AM
#14
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.

April 19th, 2009, 10:43 PM
#15
Re: Yet another question about recursion
Originally Posted by Lindley
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 5tree can stop right herethere'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

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
