Recursion Help (I don't get this)
I feel so stupid. I just can't understand recursion.
publicstaticint fib(int n)
{
int result;
if (n <=2)
{
result = 1;
}
else
{
result = fib(n-1) + fib(n-2);
}
return result;
}
The above is the famous Fibonacci method. But I DON'T GET IT. How the heck does this work? I don't understand how the recursive case works (result = fib(n-1) + fib(n-2)).
The way I understand it:
If we were to call call fib(5)...
recursive case:
result = fib(n-1) + fib(n-2); -> 4 + 3
The result would be 7, and then we would be done because we've reached the base case (n <=2). The correct answer is 5, so I'm obviously wrong. I just can't grasp this key concept. I'm feeling very noobish. :(
[1229 byte] By [
Lava_Javaa] at [2007-11-26 18:11:45]
I should add that recursion is related to [url=http://en.wikipedia.org/wiki/Mathematical_induction]mathematical induction[/url], a powerful tool in mathematics.
And once you get used to thinking about recursion, you should see that in many ways recursive solutions are simpler and clearer than non-recursive approaches.
> I should add that recursion is related to
> [url=http://en.wikipedia.org/wiki/Mathematical_induction]mathematical induction[/url], a powerful tool in
> mathematics.
>
> And once you get used to thinking about recursion,
> you should see that in many ways recursive solutions
> are simpler and clearer than non-recursive approaches.
Ever so true but an efficient recursive solution should use a stack of
depth log(n), where n is the problem size, at most. It should also not
recompute what has been computed before.
The naive recursive fibonacci function doesn't fit that bill: it uses a stack
of size n for the calculation of fib(n) and it recalculates what has been
calculated before many times.
kind regards,
Jos
> Jos,> > So true. But the OP is just learning to program. One thing at a time!Sorry Squire, 't won't happen again; I'll leave now and go flog myself ;-)kind regards,Jos
