Recursively compute the Nth Fibonacci number:

 DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Recursively compute the Nth Fibonacci number:

1. Registered User
Join Date
Apr 2005
Posts
12

## Recursively compute the Nth Fibonacci number:

so, i've got an assignment for a class that i need some help with. What i need to do is write a program that will compute a Fibonacci number using a recursive method.
i've got this:
/**
Class that recursively computes the nth Fibonacci number.
*/
public class Fib {

public static void main(String[] args) {
// Compute a few that are easy to check
for (int i = 0; i < 16; i++) {
System.out.println("F[" + i + "] = " + fib(i));
}

// Then compute some larger ones
for (int i = 2; i < 5; i++) {
System.out.println("F[" + (i * 10) + "] = " + fib(i * 10));
}
}

/**
Returns the nth Fibonacci number
*/
public static int fib(int n) {

// --------------------------------
// ----- ENTER YOUR CODE HERE -----
// --------------------------------

// --------------------------------
// --------- END USER CODE --------
// --------------------------------

}

}
but i'm somewhat confused by what i need to enter in the actual method itself. does anyone know anything about recursion or the Fibonacci numbers? i can probably explain a little better if anyone needs it. Thanks for checking this out and even more thanks to anyone who knows what to do/how to explain it to me!

Fibonacci numbers are F(0) is 1, F(1) is 1, F(2) is 2, F(3) is 3, F(4) is 5... and in general F(i+2)=[F(i) +F(i+1)]

Thanks again!
Last edited by aesoprock00; 05-02-2005 at 02:33 PM.

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
I think you would have a better time if you re-wrote your formula to be F(i) = F(i-1) + F(i-2). The progression goes fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, fib(5) = 5, fib(6) = 8, etc....

Remember for a recursive function you need to have a "base case" or two ...
F(0) = 0;
F(1) = 1;
F(2) = 1;
You can then write the function as being
F(i) = F(i-1) + F(i-2) for all i >= 3.

So you can write your binary recursive function as:

fib(n)
if( n == 1 || n == 2 )
return 1;
else
return fib(n-1) + fib(n-2)
Last edited by nspils; 05-02-2005 at 08:30 PM.

3. Registered User
Join Date
Apr 2005
Posts
12
Thanks nspils! i modified the program to:
public class Fib {

public static void main(String[] args) {
// Compute a few that are easy to check
for (int i = 0; i < 16; i++) {
System.out.println("F[" + i + "] = " + fib(i));
}

// Then compute some larger ones
for (int i = 2; i < 5; i++) {
System.out.println("F[" + (i * 10) + "] = " + fib(i * 10));
}
}

/**
Returns the nth Fibonacci number
*/
public static int fib(int n)
{

if( n == 0 || n == 1 )
return (1);
else
return fib(n-1) + fib(n-2);

}

}

and it works perfectly! Thanks for the help. i even understand it! but, where you've got if(n==1 || n==2) should actually be 0 and 1, because of the way the Fibonacci numbers work. Thanks a ton though!

What i want to do next is modify the program so that it asks the user to enter a number (possibly via bufferedReader or JOptionPane) and then give the Fibonacci number as a response to the users entered number. i'm still working on that!

4. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
You're welcome. Look again at your definitions within the Fib class. Fib(3) = 2, not 3; Fib(4) is 3, Fib(5) is 5 ... Check it out - look in your text book or run a "Google" search - the base cases are Fib(1) and Fib(2) are both 1, not Fib(0) and Fib(1) ... Since there is no definition for Fib(0), perhaps you should test to make sure that a positive integer is entered ...

A textfield, alone or inserted into some other container inserted into your GUI will be the window for inputting a value. You can use a string function to cast the value input to an int to be fed to your function, or you can use the Scanner class. There was a Java "Tech Tip" published on March 8, 2005 talking about the Scanner class as an input acceptance and evaluation tool. You can find it at:

http://java.sun.com/developer/JDCTec...05/tt0308.html
Last edited by nspils; 05-03-2005 at 01:32 AM.

5. How i see my java version from the cmd command