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

  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.

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:

    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

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

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:

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:

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.