explanation for recursion problem

[python101]

I have a python code and I don't understand how it works.
[code=python]
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
[/code]

can anyone explain how it works?

[KaezarRex]

I have a python code and I don't understand how it works.
[code=python]
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
[/code]

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.
[CODE=python]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[/CODE]
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.