Thread: Recursion: Fibonacci Number Question

How do I use rFibNum and start the loop of trials with n= 40 and determine what value of n the program fails to complete. And how would I do this with memoizedFibonocc?

Thanks for the help
//Recursion: Fibonacci Number

import java.io.*;
 
public class FibonacciNumberTest3
{
   static BufferedReader keyboard = new
             BufferedReader(new InputStreamReader(System.in));
   static int callCountint = 0;
   static long callCountlong = 0;
   public static void main(String[] args) throws IOException
    {
    int n;
    long t;
        long nthFib;
 
        String callCountStr ;
 
    for(n = 2; n < 50; n++ ){
 
 
        //stop if the size of the fib number exceeds size of int 
        // this point was determined by trial and error
        if(n>44){
            System.out.print("type enter to continue.");
            keyboard.readLine();
        }
 
 
        String nStr = String.format("%1$3s", String.valueOf(n));
 
        //initialize the array of memoized results
        for(int i = 0; i< 100; i++)
                    solvedFibs[i] = -1;
         solvedFibs[0] = 0;
         solvedFibs[1] = 1;
 
 
        //remember the start time and calculate the term
        t = System.currentTimeMillis();
 
        // pick one of the following recursion method calls
        nthFib =rFibNum( n);
        //nthFib =memoizedRecursion( n);
 
        //how long did it take
        t = System.currentTimeMillis() - t;
 
        //output the results
        System.out.print("The Fibonacci number "
                   + nStr + " is: " + String.format("%1$12s", nthFib) );
        if(callCountlong > 1000000000){
            long oneBillion = 1000000000;
            callCountlong = callCountlong / oneBillion;
            callCountStr = Long.toString(callCountlong)+" billion ";
        }else{
            if(callCountlong >= 1000000){
                callCountlong = callCountlong / 1000000;
                callCountStr = Long.toString(callCountlong)+" million ";
            }else callCountStr = Long.toString(callCountlong);
 
        }
        //format the data into nice even columns 
        //expand the strings by adding spaces to fill the column width
        // %1$24s will add spaces on the left making a 24 character column.
 
        String fibCalls = String.format("%1$12s",callCountStr);
        String callCountintStr = String.format("%1$12s",callCountint);
        System.out.println(" making ("+callCountintStr + ") "+fibCalls
                                            +" function calls taking "+t+" ms.");
        callCountint = 0;
        callCountlong = 0;
    }// end for loop
    }// end main
 
    public static long rFibNum(int n)
    {
        FibonacciNumberTest3.callCountint++;
        FibonacciNumberTest3.callCountlong++;
        if(n < 1)
                return 0;
        else if(n == 1)
                return 1;
        else
        return rFibNum( n - 1) + rFibNum( n - 2);
    }// end rFibNum
 
 
    /**
     * An array which stores calculated fibonacci numbers.
     */
    static long[] solvedFibs = new long[100];
 
    /**
     * Computes the nth fibonacci number using memoization 
     */
    static long memoizedRecursion(int n) 
    {
            //some counters for the printout of results
            FibonacciNumberTest3.callCountint++;
            FibonacciNumberTest3.callCountlong++;
 
            if (n < 1) return solvedFibs[1]; // f(0) = 0
            if (n == 1) return solvedFibs[2]; // f(1) = 1
            // If the nth fibonacci number has not been calculated we calculate it. 
            if (solvedFibs[n-2] < 0)
                    solvedFibs[n-2] = memoizedRecursion(n-2);
            if (solvedFibs[n-1] < 0)
                    solvedFibs[n-1] = memoizedRecursion(n-1);
            solvedFibs[n] = solvedFibs[n-1] + solvedFibs[n-2];
            return solvedFibs[n];
    }//end memoizedRecursion
 
 
}

This thread has been cross posted here:

http://www.java-forums.org/new-java/82542-recursion-fibonacci-number-question.html
http://www.coderanch.com/t/621281/java/java/Recursion-Fibonacci-Number

Although cross posting is allowed, for everyone's benefit, please read:

Java Programming Forums Cross Posting Rules

The Problems With Cross Posting

Has been told about this before:
http://www.javaprogrammingforums.com...ogramming.html
http://www.javaprogrammingforums.com...ogramming.html

db

F(n) = F(n-1) + F(n-2);

F(0) = 0;
F(1) = 1;


At which value of n?

add a throws clause (throws InputMismatchException) to your two methods (rfib and memorized).

Then, when you call them in your for loop, put a try/catch block around each iteration like this


try
{


}

catch(InputMismatchException ime)
{
System.out.println(n);
break;
}


It will stop your for loop though when it throws the exception. If you don't want it to stop when you reach that point and instead just tell them to hit enter, remove the "break;"
Then it will just print out the n value where it stopped working.

not what I'm asking for exactly. How do I use rFibNum and start the loop of trials with n= 40

for(n = 40; n < 50; n++ )
{
...........

}

public class F {


int fibo (int f) { if (f=0)return 0;
else if (f=1) return 1;
else return fibo(f-1)+fibo(f-2);
}
System.out.print(fibo(3));

}

What is incorrect in this code as the compiler show 5 errors in System.out.print..-some identifiers expected, illegal start of type