explanation for recursion problem

[python101]

I have a python code and I don't understand how it works.

def cal(n):
    print 'n =', n
    if n<=1:
        return n
    else:
        return cal(n-1) + cal(n-2)
#when I run
>>cal(4)
n = 4  # it is because I use parameter 4
n = 3  # is it because of cal(n-1), n=4-1?
n = 2  # is it because of cal(n-2), n=4-2? the rest I can get 
n = 1
n = 0
n = 1
n = 2
n = 1
n = 0
3
 

can anyone explain how it works?

[KaezarRex]

I have a python code and I don't understand how it works.

def cal(n):
    print 'n =', n
    if n<=1:
        return n
    else:
        return cal(n-1) + cal(n-2)
#when I run
>>cal(4)
n = 4  # it is because I use parameter 4
n = 3  # is it because of cal(n-1), n=4-1?
n = 2  # is it because of cal(n-2), n=4-2? the rest I can get 
n = 1
n = 0
n = 1
n = 2
n = 1
n = 0
3
 

can anyone explain how it works?

The "cal(n-1)" in the return statement always happens first because it's farther to the left, and each of their "cal(n-1)"'s happen first.

n = 4  # it is because I use parameter 4
n = 3  # cal(n-1), n=4-1
n = 2  # cal(cal(n-1)-1), n=4-1-1
n = 1  # cal(cal(cal(n-1)-1)-1), n=4-1-1-1
n = 0
n = 1
n = 2
n = 1
n = 0

Sometimes it helps to visualize whats going on as a tree.

cal
        4
      /   \
    3   +   2
   / \     / \
  2 + 1   1 + 0
 / \ 
1 + 0

The order the calls happen zig-zags from the very top, all the way down the left edge (4, 3, 2, 1), then from the 0 at the very bottom, back up to the other 2 (0, 1, 2), and then back down to the last remaining 1 (1), then finally to the farthest right number (0).
That probably didn't make any sense, but hopefully the commented output will help.

[python101]

Thanks for your explanation, now I understand why it prints out n = ...
but I still don't understand why the final line is 3

[KaezarRex]

Thanks for your explanation, now I understand why it prints out n = ...
but I still don't understand why the final line is 3

3 is the sum of all of the leaf nodes of the tree.