By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
444,050 Members | 1,020 Online
Bytes IT Community
+ Ask a Question
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
  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
Share this Question
Share on Google+
3 Replies


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

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

KaezarRex
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

Post your reply

Sign in to post your reply or Sign up for a free account.