Hi
I just started reading about recursion so I'm not sure how things work. I can find general information about recursion but not as analytical as I would like it to be.
Say I have this code that computes Fibonacci numbers... -
public static long fib(int n){
-
-
if (n <= 1)
-
return 1;
-
else
-
return fib(n-1) + fib(n-2);
-
}
-
Say now that n = 5.
What exactly happens when line 6 is read? The method should return fib(4) + fib(3). Does it first compute fib(4) and only when it has a result computes fib(3)?
I understand than in order to compute fib(4) or fib(3) it has first to compute fib(2) and fib(1) which is the base case but I'm confused about the order in which this works.
Thanks a lot,
stack
7 1296
I believe that the first call to fib in the return statement is evaluated first. The call to fib, then, looks like this: - n = 5
-
fib(5);
-
5 > 1, so
-
fib(4);
-
4 > 1, so
-
fib(3);
-
3 > 1, so
-
fib(2);
-
2 > 1, so
-
fib(1);
-
1 <= 1, so return 1;
-
fib(0);
-
0 <= 1, so return 0;
-
return 1+0;
-
-
fib(1);
-
1 <= 1, so return 1;
-
return 1+1;
-
-
fib(2);
-
2 > 1, so
-
fib(1);
-
1 <= 1, so return 1;
-
fib(0);
-
0 <= 1, so return 0;
-
return 1+0;
-
return 2+1;
-
-
fib(3);
-
3 > 1, so
-
fib(2);
-
2 > 1, so
-
fib(1);
-
1 <= 1, so return 1;
-
fib(0);
-
0 <= 1, so return 0;
-
return 1+0;
-
fib(1);
-
1 <= 1, so return 1;
-
return 1+1;
-
return 3+2;
-
See how many function calls are made for a very small initial value? That's why using recursion to find Fibonacci numbers is a TERRIBLE idea. But that's how the recursion works.
See how many function calls are made for a very small initial value? That's why using recursion to find Fibonacci numbers is a TERRIBLE idea. But that's how the recursion works.
Of course, don't generalize from this that recursion is *bad*. There are many problems, like sorting data, where the optimal solution can be done with recursion. And there are many problems where recursion is the clearest, simplest, most logical and most elegant solution.
Hi
I just started reading about recursion so I'm not sure how things work. I can find general information about recursion but not as analytical as I would like it to be.
Say I have this code that computes Fibonacci numbers... -
public static long fib(int n){
-
-
if (n <= 1)
-
return 1;
-
else
-
return fib(n-1) + fib(n-2);
-
}
-
Say now that n = 5.
What exactly happens when line 6 is read? The method should return fib(4) + fib(3). Does it first compute fib(4) and only when it has a result computes fib(3)?
I understand than in order to compute fib(4) or fib(3) it has first to compute fib(2) and fib(1) which is the base case but I'm confused about the order in which this works.
Thanks a lot,
stack
Realize that these questions have little or nothing to do with recursion. What if the code had been: -
public static long fib(int n){
-
if (n <= 1)
-
return 1;
-
else
-
return gib(n-1) + hib(n-2);
-
}
-
The questions you raise are just as valid for this function. So why didn't you ask them before you got to studying recursion? I think people are subtlely taught that recursion is hard, when I honesty believe it's easier than a lot of other things to understand, for example, loops.
Of course, don't generalize from this that recursion is *bad*. There are many problems, like sorting data, where the optimal solution can be done with recursion. And there are many problems where recursion is the clearest, simplest, most logical and most elegant solution.
Exactly. Another great example of recursion can be found in many of the popular solutions to tree problems, such as searching, inserting, etc. Even though these can be solved with loops, recursion is a very intuitive solution.
- n = 5
-
fib(5);
-
5 > 1, so
-
fib(4);
-
4 > 1, so
-
fib(3);
-
3 > 1, so
-
fib(2);
-
2 > 1, so
-
fib(1);
-
1 <= 1, so return 1;
-
fib(0);
-
0 <= 1, so return 0;
-
return 1+0;
-
.....
-
-
This is the kind of answer I was hoping for. Thank you very much.
One more thing. The "return 0" should be "return 1", right?
Reagards,
stack
Ah, yes - in your example. Some recursive fib. sequence functions return 0 if n is 0, or 1 if n is 1. It doesn't affect the series very much, just puts a 0 in front, and this is how I assumed it would be written. So...all the returns are wrong, but do you get the idea of how a simple call to fib() is evaluated?
Ah, yes - in your example. Some recursive fib. sequence functions return 0 if n is 0, or 1 if n is 1. It doesn't affect the series very much, just puts a 0 in front, and this is how I assumed it would be written. So...all the returns are wrong, but do you get the idea of how a simple call to fib() is evaluated?
I draw a tree for all fib calls where every node has 2 children (n-1) and (n-2) and now everything makes sense :-)
Thanks again!
stack
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Peri |
last post by:
I'm trying to create Python parser/interpreter using ANTLR.
Reading grammar from language refference I found:
or_expr::= xor_expr | or_expr "|" xor_expr
For me it looks like infinite recursion....
|
by: da Vinci |
last post by:
Greetings.
I want to get everyone's opinion on the use of recursion.
We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted...
|
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;
|
by: Csaba Gabor |
last post by:
I suppose spring fever has hit at alt.math.undergrad since I didn't get
any rise from
them when I posted this a week ago, so I am reposting this to some of
my favorite
programming groups:
I'm...
|
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...
|
by: Kay Schluehr |
last post by:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
|
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...
|
by: robert |
last post by:
My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception.
What...
|
by: athar.mirchi |
last post by:
..plz define it.
|
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 ??
|
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...
|
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: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
| |