471,312 Members | 1,903 Online

# explanation for recursion problem 90
I have a python code and I don't understand how it works.
Expand|Select|Wrap|Line Numbers
1. def cal(n):
2.     print 'n =', n
3.     if n<=1:
4.         return n
5.     else:
6.         return cal(n-1) + cal(n-2)
7. #when I run
8. >>cal(4)
9. n = 4  # it is because I use parameter 4
10. n = 3  # is it because of cal(n-1), n=4-1?
11. n = 2  # is it because of cal(n-2), n=4-2? the rest I can get
12. n = 1
13. n = 0
14. n = 1
15. n = 2
16. n = 1
17. n = 0
18. 3
19.
can anyone explain how it works?
Dec 4 '07 #1
3 1355 KaezarRex
52 I have a python code and I don't understand how it works.
Expand|Select|Wrap|Line Numbers
1. def cal(n):
2.     print 'n =', n
3.     if n<=1:
4.         return n
5.     else:
6.         return cal(n-1) + cal(n-2)
7. #when I run
8. >>cal(4)
9. n = 4  # it is because I use parameter 4
10. n = 3  # is it because of cal(n-1), n=4-1?
11. n = 2  # is it because of cal(n-2), n=4-2? the rest I can get
12. n = 1
13. n = 0
14. n = 1
15. n = 2
16. n = 1
17. n = 0
18. 3
19.
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.
Expand|Select|Wrap|Line Numbers
1. n = 4  # it is because I use parameter 4
2. n = 3  # cal(n-1), n=4-1
3. n = 2  # cal(cal(n-1)-1), n=4-1-1
4. n = 1  # cal(cal(cal(n-1)-1)-1), n=4-1-1-1
5. n = 0
6. n = 1
7. n = 2
8. n = 1
9. n = 0
Sometimes it helps to visualize whats going on as a tree.
Expand|Select|Wrap|Line Numbers
1. cal
2.         4
3.       /   \
4.     3   +   2
5.    / \     / \
6.   2 + 1   1 + 0
7.  / \
8. 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.
Dec 4 '07 #2
python101
90 Thanks for your explanation, now I understand why it prints out n = ...
but I still don't understand why the final line is 3
Dec 5 '07 #3
KaezarRex
52 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.
Dec 5 '07 #4