444,050 Members | 1,020 Online Need help? Post your question and get tips & solutions from a community of 444,050 IT Pros & Developers. It's quick & easy.

# explanation for recursion problem

 P: 90 I have a python code and I don't understand how it works. Expand|Select|Wrap|Line Numbers 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? Dec 4 '07 #1
3 Replies

 P: 52 I have a python code and I don't understand how it works. Expand|Select|Wrap|Line Numbers 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. Expand|Select|Wrap|Line Numbers 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. Expand|Select|Wrap|Line Numbers 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. Dec 4 '07 #2

 P: 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

 P: 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 