Answer to Question #86644 in Algorithms for Mlk

Question

Implement the basic recursive implementation of Fibonacci number function and find the largest Fibonacci number that your computer can compute. The algorithm is as follows:
int Fib(int n)
{
 if(n<2) return n;
 return Fib(n-1) + Fib(n-2);
}

Answer 1

Question:

Implement the basic recursive implementation of Fibonacci number function and find the largest Fibonacci number that your computer can compute. The algorithm is as follows: 

int Fib(int n)

{ if(n<2) return n;

return Fib(n-1) + Fib(n-2);

}

Answer:

import java.util.Scanner;

public class Fibonacci {

  public static long fib(long n) {

    if (n < 2) {

      return n;

    } else {

      return fib(n - 1) + fib(n - 2);

    }

  }

  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    // 10459

    System.out.println("Enter a number: ");

    long i = in.nextLong();

    System.out.printf("Fibonacci of %d = %d\n", i, fib(i));

  }

}

The maximum Fibonacci number, that my computer is not able to calculate due to the StackOverflowError, is 10460:

Therefore, the largest Fibonacci number that my computer can compute is 10459. However it will take forever to get a result, as long as the algorithm is written recursively.