• Advertisement

Archived

This topic is now archived and is closed to further replies.

help with basic recursion

This topic is 5828 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This code came from Sams teach yourself C++ in 21 days by Jesse Liberty. Can anybody clarify this for me? I have my questions on the line of trouble. Thanks in advance. A. #include <iostream.h> int fib (int n); int main() { int n, answer; cout << "Enter number to find: "; cin >> n; cout << "\n\n"; answer = fib(n); cout << answer << " is the " << n << "th Fibonacci number\n"; return 0; } int fib (int n) { cout << "Processing fib(" << n << ")... "; if (n < 3 ) { cout << "Return 1!\n"; return (1);/* Where''s this returning to? What''s it doing? It doesn''t go back to main, because it happens alot.*/ } else { cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n"; return( fib(n-2) + fib(n-1));/* same here, where does this go, what''s it doing?*/ } }

Share this post


Link to post
Share on other sites
Advertisement
If you called fib(3), you''d get the one in main. Since you don''t however, other invocations of fib get it.

Recursive functions call themselves. How? A function is just code; a recursive function just passes new arguments to more code and gets a result from that. And finally, after unwinding the stack, it returns a value to you. Presto!

[ GDNet Start Here | GDNet Search Tool | GDNet FAQ | MS RTFM [MSDN] | SGI STL Docs | Google! ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
lets try an example to see this thing in action, that should help clarify whats going on.

Lets say that the user enters 5.
main() will call fib(5).

fib will use the else part of the if statement because 5 isn't less than 3.
now this statement:

return( fib(n-2) + fib(n-1));

could be written like this (which will hopefully make this recursion gear easier to understand)

int ans = fib(n-2) + fib(n-1);
return ans;

these 2 are equivelant, agreed?

OK now we work out what ans is going to be.
ans is fib(5-2) + fib(5-1)
ie. fib(3) + fib(4)
now the program will run fib(3) first before it runs fib(4)
so lets do that.

---fib(3)---
here we will again take the else part of the if statement
and a new version of ans will be created (in fact a new
version of every variable used in fib() is created when it calls
itself, or when anyting else calls it too)
this ans will be fib(3-2) + fib(3-1)
this is
ans = fib(1) + fib(2)
lets evaluate this
When fib(1) is called we take the first part of the if which say:
return(1);
therefore fib(1) evaluates to 1.
now that we have evaluated fib(1) we can evaluate fib(2)
(because ans = fib(1) + fib(2) )
fib(2) will take the first part of the if again (as 2 IS lessthan 3)
this will return(1), therefore fib(2) evaluates to 1 as well.
Therefore ans = fib(2) + fib(1)
evaluates to ans = 1 + 1 = 2.
remember this ans is being returned by the call to fib(3)

therefore fib(3) evaluates to 2.

Now remember way up there where I wrote:
ans is fib(5-2) + fib(5-1)
ie. fib(3) + fib(4)

well now we've evaluated fib(3) (which is 2)
and now we have to evaluate fib(4).


---fib(4)---
fib(4) will take the else part of the if because 4 isn't less than 3. Therefore it will calculate a new ans , which
will be:
ans = fib(4-2) + fib(4-1)
ie. ans = fib(2) + fib(3)
now we've already calculated both fib(2) and fib(3) so I won't
go through them again. The answer will be the same because we're
calling the exact same function (fib() ) with the same
parameter (2 or 3) as before. It isn't always true that calling
the same function with the same parameter will produce the exact same result, but it is true in this case because fib() doesn't have any side effects - this means it doesn't alter anything
except variables which are declared inside itself.
There fore we know that ans will be:
fib(2) + fib(3) = 1 + 2 = 3.
therefore this call to fib(4) will return 3.

Finally we go back to the original statement that said
ans = fib(3) + fib(4)
we now have worked out fib(3) and fib(4) and so can add them
together.
fib(3) = 2
fib(4) = 3.
therefore ans = 2+3 = 5.
therefore the call to fib(5) returns 5.
this 5 is returned to main() and it is the final answer
that is printed by main().

I hope that helps. A good thing to remeber is to always to a
"hand trace" of your code like this when you don't get it, to
see whats going on. Just follow it through with a pen and paper
much the same way as I've done here and stuff like this should
work out OK.

For a real good understanding of this try tracing through
fib(6) and see if you can get the anser of 8.

good luck
Toby


Edited by - tobymurray on February 4, 2002 11:01:34 PM

Edited by - tobymurray on February 4, 2002 11:03:05 PM

Edited by - tobymurray on February 4, 2002 11:05:09 PM

Share this post


Link to post
Share on other sites
I doubt that you''re going to read this again Toby, but thanks alot for your help. I understand it completely now.
A.

Share this post


Link to post
Share on other sites

  • Advertisement