CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Member
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. Elite Member
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

3. Member +
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. Member
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. Member +
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. Member
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. Member
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...

Last edited by davide++; April 14th, 2009 at 12:18 PM.

8. Member
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. 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. Member
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. std
Junior Member
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.

12. Member
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. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

## 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 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. 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. Member
Join Date
Feb 2006
Posts
127

## 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 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
•