# programming the Fibonacci number

• July 14th, 2012, 06:26 PM
johnmerlino
programming the Fibonacci number
the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

So I would expect output like this:

0,1,1,2,3,5...

Code :

``` private static int fib(int k) { if (k < 2) { return k; } return fib(k-1) + fib(k-2); }```

If k is equal to 2, fib(k-1) returns 1 and fib(k-2)returns -1 (because after first recursion call, k will equal 1 and 1-2=-1). So when we add 1 + -1, we get 0. Obviously, Im not following something here because what we should have is 1 + 2 to get 3.

thanks for explanation.
• July 15th, 2012, 12:30 AM
Zaphod_b
Re: programming the Fibonacci number
Quote:

Originally Posted by johnmerlino
...
So I would expect output like this:

0,1,1,2,3,5...

Well, isn't that what happens when you call the function with values of 0, 1, 2, 3, 4, 5, ...

(Did you try it?)

Quote:

Originally Posted by johnmerlino
...If k is equal to 2, fib(k-1) returns 1

OK! I'm with you so far.

Quote:

Originally Posted by johnmerlino
and fib(k-2)returns -1

No. According to the code, for k = 1, since that is less than 2, the function returns the value of its argument (returns 1).
Quote:

Originally Posted by johnmerlino
(because after first recursion call, k will equal 1

Not true. When you call a function (recursively or not) with an int argument, changes the function makes internally with the parameter do not cause changes of the argument back in the calling function. That's fundamental. The calling function is not "sending it k to work with," it is sending it the value of k. The function works on its own copy of the parameter.

If you have trouble following the code "in your head," try it with pencil and paper. Step through it for k = 2.

Sometimes it is helpful to make the program tell you what it is working with at each step:
Code java:

``` private static int fib(int k) { System.out.println("Into fib with k = " + k);   if (k < 2) { System.out.println(" fib(" + k + ") returning " + k); return k; }   System.out.println("In fib(" + k + ") calling fib(" + (k-1) + ")"); int i1 = fib(k-1); System.out.println(" After calling fib(" + (k-1) + ") return value = " + i1 + ", k = " + k);   System.out.println("In fib(" + k + ") calling fib(" + (k-2) + ")"); int i2 = fib(k-2); System.out.println(" After calling fib(" + (k-2) + ") return value = " + i2 + ", k = " + k); return i1+i2; }```

If you call this with k = 2, you should see
Code :

```Into fib with k = 2 In fib(2) calling fib(1) Into fib with k = 1 fib(1) returning 1 After calling fib(1) return value = 1, k = 2 In fib(2) calling fib(0) Into fib with k = 0 fib(0) returning 0 After calling fib(0) return value = 0, k = 2 fib(2) = 1```

(Note that I separated the two recursive calls so that I could show the results separately. In java, putting the two calls in a single expression gives the same result that I showed as the expression is evaluated left-to-right.

Cheers!

Z
• July 15th, 2012, 09:59 PM
johnmerlino
Re: programming the Fibonacci number
Quote:

Originally Posted by Zaphod_b
Well, isn't that what happens when you call the function with values of 0, 1, 2, 3, 4, 5, ...

(Did you try it?)

OK! I'm with you so far.

No. According to the code, for k = 1, since that is less than 2, the function returns the value of its argument (returns 1).

Not true. When you call a function (recursively or not) with an int argument, changes the function makes internally with the parameter do not cause changes of the argument back in the calling function. That's fundamental. The calling function is not "sending it k to work with," it is sending it the value of k. The function works on its own copy of the parameter.

If you have trouble following the code "in your head," try it with pencil and paper. Step through it for k = 2.

Sometimes it is helpful to make the program tell you what it is working with at each step:
Code java:

``` private static int fib(int k) { System.out.println("Into fib with k = " + k);   if (k < 2) { System.out.println(" fib(" + k + ") returning " + k); return k; }   System.out.println("In fib(" + k + ") calling fib(" + (k-1) + ")"); int i1 = fib(k-1); System.out.println(" After calling fib(" + (k-1) + ") return value = " + i1 + ", k = " + k);   System.out.println("In fib(" + k + ") calling fib(" + (k-2) + ")"); int i2 = fib(k-2); System.out.println(" After calling fib(" + (k-2) + ") return value = " + i2 + ", k = " + k); return i1+i2; }```

If you call this with k = 2, you should see
Code :

```Into fib with k = 2 In fib(2) calling fib(1) Into fib with k = 1 fib(1) returning 1 After calling fib(1) return value = 1, k = 2 In fib(2) calling fib(0) Into fib with k = 0 fib(0) returning 0 After calling fib(0) return value = 0, k = 2 fib(2) = 1```

(Note that I separated the two recursive calls so that I could show the results separately. In java, putting the two calls in a single expression gives the same result that I showed as the expression is evaluated left-to-right.

Cheers!

Z

thanks for response
• July 26th, 2012, 12:22 AM
aesguitar
Re: programming the Fibonacci number
One thing to mention, calculating terms in the Fibonacci sequence recursively is a bad idea, the resulting program uses too much memory and eventually takes a very long time to run.

Test class code:

Code java:

```package algorithms;   import java.math.BigInteger;   public class FibonacciSequence {   public FibonacciSequence() {}   public static BigInteger recFibSeq(int num) { if(num <= 2) { return BigInteger.ONE; } else { return recFibSeq(num-1).add(recFibSeq(num-2)); } }   public static BigInteger loopFibSeq(int num) {   // Declare BigInteger variables for sum, nminus1 and nminus2 BigInteger sum = BigInteger.ZERO; // Initialize sum to zero and the others to 1 BigInteger minus1 = BigInteger.ONE, minus2 = BigInteger.ONE;   if( num <= 2) { return BigInteger.ONE; } // x <= 2 else { for (int i = 3; i <= num; i++) { // Set sum equal to nminus1 + nminus2 sum = minus1.add(minus2); // Set nminus2 equal to nminus1 minus2 = minus1; // Set nminus1 equal to sum minus1 = sum; } // for } // else return sum; }     public static void main(String[] args) { int num = 40;   System.out.println("Shows difference in time between calculating a term in the Fibonacci sequence recursively and with a loop. Calculates the 40th term in the sequence.\n");   long start = System.currentTimeMillis(); System.out.println("Recursive: " + recFibSeq(num)); long end = System.currentTimeMillis(); System.out.println("Elapsed time: " + (end-start) + "ms.\n");   start = System.currentTimeMillis(); System.out.println("Looped: " + loopFibSeq(num)); end = System.currentTimeMillis(); System.out.println("Elapsed time: " + (end-start) + "ms."); } }```

Output:

Code :

```Shows difference in time between calculating a term in the Fibonacci sequence recursively and with a loop. Calculates the 40th term in the sequence.   Recursive: 102334155 Elapsed time: 8849ms.   Looped: 102334155 Elapsed time: 0ms.```