The flow of a Recursive Call
I looked for answers for this question but most were given in programming languages other than Python.
Now in this code:
def f(n): if n==0: return 1 else: m = f(n-1) s = n * m return s
I know that if I use n = 3 for instance, the function will use the second branch to calculate "3-1 = 2" then will move to do the same with "2-1 = 1" getting in the end to 0 then the result will be returned. Now what would happen in the following case:
def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2)
Let's say we execute it with n = 5. The third branch will then be used to return fib(4) + fib(3). But what then? Which number would the program use as the new value of n, 4 or 3? Thank you.
The recursion level that is given 5 as a parameter will call itself twice, once with 4 and once with 3, and the results of those two calls will be added together.
Similarly, calling it with 4 will result in two calls, one with 3 and one with 2. And so on down through the levels. So the recursion "tree" would be:
_____5_____ / \ __4__ 3 / \ / \ 3 2 2 1 / \ / \ / \ 2 1 1 0 1 0 / \ 1 0
Your more "classical" recursion like factorial only calls itself once per level but that's by no means necessary for something to be recursive:
5 \ 4 \ 3 \ 2 \ 1
If you want to see what's going on, change it to something like this:
def fibonacci(x, n): for i in range(x): print " ", print "Level %d called with %d"%(x,n) if n == 0: return 0 if n == 1: return 1 return fibonacci(x+1,n-1) + fibonacci(x+1,n-2) print fibonacci (0,5)
The output generated:
Level 0 called with 5 Level 1 called with 4 Level 2 called with 3 Level 3 called with 2 Level 4 called with 1 Level 4 called with 0 Level 3 called with 1 Level 2 called with 2 Level 3 called with 1 Level 3 called with 0 Level 1 called with 3 Level 2 called with 2 Level 3 called with 1 Level 3 called with 0 Level 2 called with 1 5
You'll see I've also removed the totally unnecessary else-after-return paradigm that some people use. It's rarely needed and can make code less readable.
Having explained that, you should also make yourself aware of the situations in which recursion can be abused. Although the Fibonacci sequence can be coded elegantly as a recursive solution, it's not overly efficient since it recalculates a lot of different values in each sub-branch (such as fib(2) being calculated three times in the given example, and a lot more times if you call it with a larger argument than 5).
Even factorial is not that good for recursion since it reduces the "search space" quite slowly: fact(20) will in fact go about twenty-deep on the stack, and the stack is often a limited resource.
The best recursive algorithms are those that reduce the search space quickly, such as a binary search, which halves it on every recursion level.
Knowing when to use recursion is usually just as important than knowing how to.
You can get away with iterative solutions for both factorial and Fibonacci, as with:
def fact (n): # n = 1..whatever result = n for i in range (2,n): result = result * n def fib(n): # n = 1..whatever me = 1 if n >1: grandparent = 1 parent = 1; for i in range(2, n): me = parent + grandparent grandparent = parent parent = me return me
Neither of these will risk exhausting the stack for large volumes of n