473,326 Members | 2,125 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

explanation for recursion problem

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 1424
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
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
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

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

Similar topics

43
by: Lorenzo Villari | last post by:
I've tried to transform this into a not recursive version but without luck... #include <stdio.h> void countdown(int p) { int x;
10
by: paulw | last post by:
Hi Please give problems that "HAS TO" to use recursion (recursive calls to itself.) Preferrably real world examples, not knights tour. I'm thinking about eliminating the use of stack... ...
75
by: Sathyaish | last post by:
Can every problem that has an iterative solution also be expressed in terms of a recursive solution? I tried one example, and am in the process of trying out more examples, increasing their...
18
by: MTD | last post by:
Hello all, I've been messing about for fun creating a trial division factorizing function and I'm naturally interested in optimising it as much as possible. I've been told that iteration in...
6
by: Andre Kempe | last post by:
hej folks. i have a heap with fixed size and want to determine the depth of a element with given index at compile-time. therefore i wrote some templates. however, when i use template...
12
by: NOO Recursion | last post by:
Hi everyone! I am trying to write a program that will search a 12x12 for a thing called a "blob". A blob in the grid is made up of asterisks. A blob contains at least one asterisk. If an...
13
by: Mumia W. | last post by:
Hello all. I have a C++ program that can count the YOYOs that are in a grid of Y's and O's. For example, this Y O Y O O Y O Y O Y O O Y O Y Y O Y O Y O O Y O O Y Y O Y O
2
by: Victor Lin | last post by:
Hi, I encounter a problem with pickle. I download a html from: ...
30
by: Jeff Bigham | last post by:
So, it appears that Javascript has a recursion limit of about 1000 levels on FF, maybe less/more on other browsers. Should such deep recursion then generally be avoided in Javascript?...
35
by: Muzammil | last post by:
int harmonic(int n) { if (n=1) { return 1; } else { return harmonic(n-1)+1/n; } } can any help me ??
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.