Question

The Fibonacci sequence is the series of integers

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 . . .

See the pattern? Each element in the series is the sum of the preceding two elements. Here is a recursive formula for calculating the nth number of the sequence:

Fib(N) = {N, if N = 0 or 1

Fib(N - 2) + Fib(N - 1), if N > 1

a) Write a recursive method fibonacci that returns the nth Fibonacci number when passed the argument n.

b) Write a non recursive version of the method fibonacci.
c) Write a driver to test your two versions of the method fi‐
bonacci.
d) Compare the recursive and iterative versions for efficiency.
(Use words, not O( ) notation.)

Use Java programming.

Answer 1

//Fibonacci.java
import java.util.Scanner;

public class Fibonacci {
    public static int FibR( int n){
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        else{
            return FibR(n-1) + FibR(n-2);
        }
    }

    public static int FibI( int n){
        int a = 0,b = 1,c = 1;
        if(n == 0){
            return a;
        }
        if(n == 1){
            return b;
        }
        else{
            while(n>1){
                c = a + b;
                a = b;
                b = c;
                n--;
            }
            return c;
        }
    }

    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int n;
        System.out.println("Input an integer for the index of a term in the Fibonacci sequence:");
        n = scanner.nextInt();
        System.out.println("\nthe "+(n)+"-th term \""+FibR(n)+"\" in the Fibonacci sequence can be computed recursively.");
        System.out.println("the "+(n)+"-th term \""+FibI(n)+"\" in the Fibonacci sequence can be computed recursively.");
    }
}

Time complexity of recursive version is O(2^n)
Time complexity of iterative version is O(n)