The flow of a Recursive Call
Question: 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.


Answer: 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`

