Recursively compute the Nth Fibonacci number:


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 5 of 5

Thread: Recursively compute the Nth Fibonacci number:

  1. #1
    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. #2
    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. #3
    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. #4
    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. #5
    Join Date
    Nov 2009
    Location
    Sri Lanka
    Posts
    1
    How i see my java version from the cmd command

    please tell me...........thanks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center