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.