Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Help Understanding Recursion

recursion

  • Please log in to reply
6 replies to this topic

#1 Agent001

Agent001

    CC Regular

  • Member
  • PipPipPip
  • 41 posts

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

    CC Regular

  • Member
  • PipPipPip
  • 37 posts
  • 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,
Posted Image


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

    CC Regular

  • Member
  • PipPipPip
  • 41 posts

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 :D
  • 0

#4 Yonatan

Yonatan

    CC Regular

  • Member
  • PipPipPip
  • 37 posts
  • 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

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 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

    CC Regular

  • Member
  • PipPipPip
  • 37 posts
  • 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
  • PipPipPipPipPipPipPipPip
  • 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