•

Check out our Community Blogs Register and join over 40,000 other developers!

### Popular Tags      # Help Understanding Recursion

recursion

6 replies to this topic

### #1 Agent001

Agent001

Posted 24 June 2012 - 11:59 AM

Hi there people. After a while, i'm back...

So, anyways, i'm looking into recursion, and it's a little abstract for me...

```int f(int p) {
if (p == 0) return 1;
if (p == 1) return 2;
return f(p-1)*f(p-2);
}
#include <stdio.h>
int main() {
printf("%d %d", 4, f(4));
return 0;
}
```

For example, the code above. I can't exactly seem to figure out what the function f does.

Could someone break down the code, like i'm dumb as a brick, the part with f function especially.
• 0

### #2 Yonatan

Yonatan
• Location:Israel
• Programming Language:C, Java, C++, C#, JavaScript, PL/SQL, Visual Basic .NET
• Learning:Python, JavaScript

Posted 24 June 2012 - 01:10 PM

f(int p) returns the p element in the following series:

1,2,2,4,8,32,(32*8), 32*(32*8)...

In other words the multiplication of the previous 2 elements, --- In order to solve those kind of problems I strongly recommend choosing a small p (4 for example) and trying it on paper.

f(4) = f(3)*f(2)
f(3) = f(2)*f(1)
f(2) = f(1)*f(0)

f(1) = 2
f(0) = 1

thus,
f(2) = 2, f(3) = 4, f(4)=8.
• 0

### #3 Agent001

Agent001

Posted 24 June 2012 - 01:35 PM

Hm, i typed the code in VS, and saw that the program should write 4 8.
So, 8 should be the result of the f function.

Then i broke down the code, to see it clearly what's going on.

Anyways, am i getting this right - when i call f(4) - in the first isteration i have
return f(3)*f(2)

then i look what's f(3) - it's f(2)*f(1), and f(2) is f(1)*f(0), that is 2*1 = 2
then f(2)*f(1) would be 2*2 = 4 => so, f(3)=4.

since i already know that f(2)=2 => f(3)*f(2) = 4*2 = 8?

Did i get it right • 0

### #4 Yonatan

Yonatan
• Location:Israel
• Programming Language:C, Java, C++, C#, JavaScript, PL/SQL, Visual Basic .NET
• Learning:Python, JavaScript

Posted 24 June 2012 - 01:36 PM

Yes.
• 0

### #5 Flying Dutchman

Flying Dutchman

• Expert Member
•       • 1090 posts
• Location:::1
• Programming Language:C++, Python

Posted 26 June 2012 - 05:37 AM

```f(4) = 2 * 4
|
+--> f(3) * f(2) = 2 * 2 * 2
|	|
|	+--> f(1) * f(0) = 2
|		2  *   1
|
+--> f(2) * f(1) = 2 * 2
|  *   2
|
+--> f(1) * f(0) = 2
2  *   1
```

You can see that f(2) gets computed twice. It's not a problem for small inputs, but it drastically adds to total time when using bigger numbers.
• 0

The roots of education are bitter, but the fruit is sweet.

### #6 Yonatan

Yonatan
• Location:Israel
• Programming Language:C, Java, C++, C#, JavaScript, PL/SQL, Visual Basic .NET
• Learning:Python, JavaScript

Posted 26 June 2012 - 10:13 AM

You can use a Data Structure that mapps int number to int result in order to prevent unnecessary calculations.
• 0

### #7 chili5

chili5

CC Mentor

• Expert Member
•        • 3038 posts
• Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
• Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 26 June 2012 - 11:00 AM

To solve the problem of repeated calculations you can use a technique called memoization. Basically you store computed values in a table to reduce the number of useless function calls. For fibonacci, the classic algorithm memoization gives you a linear time algorithm. Without storing values the recursive solution for fibonacci is an exponential algorithm. The downside is you are using more memory.
• 0

### Also tagged with one or more of these keywords: recursion

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download