Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: programming the Fibonacci number

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

2. ## Re: programming the Fibonacci number

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

Originally Posted by johnmerlino
...If k is equal to 2, fib(k-1) returns 1
OK! I'm with you so far.

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).
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:
```    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

3. ## Re: programming the Fibonacci number

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

4. ## 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:

```package algorithms;

import java.math.BigInteger;

public class FibonacciSequence {

public FibonacciSequence()
{}

public static BigInteger recFibSeq(int num)
{
if(num <= 2)
{
return BigInteger.ONE;
}
else
{
}
}

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