New to recursion

[stack]

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

[Ganon11]

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.

[BigDaddyLH]

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.

[BigDaddyLH]

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

[CODE=Java]
public static long fib(int n){

if (n <= 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
[/CODE]

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:
[CODE=Java]
public static long fib(int n){
if (n <= 1)
return 1;
else
return gib(n-1) + hib(n-2);
}
[/CODE]
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.

[Ganon11]

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.

[stack]

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

[Ganon11]

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?

[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?

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