Question

Write a recursive and an iterative function to calculate the nth element in a Fibonacci sequence. A Fibonacci sequence is defined as the element 1, followed by another 1, and each element thereafter is the sum of the previous two elements. For example, the first 9 elements of a Fibonacci sequence are:

• 1 2 3 5 8 13 21 34

This famous sequence was originally used to predict the growth of rabbit populations!

Once you have each of the functions working for n equal to 40, determine which method is more efficient by timing the two separate function calls and printing out the time required for each method call to return the 40^th element in the sequence. Return the 40^th element to main and print it. After that, print out a complete Fibonacci sequence from element 1 to element 40, along with its position number.

1. 1
2. 1
3. 2
4. 3

.       .

.       .

This last part should not be timed.

The timer function you need for this Project is:

                        Date d1 = new Date();

                        long milliseconds = D1.getTime();

                                                OR

                        long start = System.currentTimeMillis();

Turn in the source, output, and a short paragraph explaining the reason the two methods took different amounts of time to execute.

Please write in JAVA

and please write recursive part and iterative part separate!

Answer 1

Thanks for the question.


Below is the code you will be needing  Let me know if you have any doubts or if you need anything to change.


Thank You !!


===========================================================================

import java.util.Date;

public class Fibbonacci {

    public static int recursiveFibbonacci(int nthTerm) {
        if (nthTerm <= 1)
            return 1;
        return recursiveFibbonacci(nthTerm - 1) + recursiveFibbonacci(nthTerm - 2);
    }


    public static int iterativeFibbonacci(int nthTerm) {
        if (nthTerm <= 1) {
            return 1;
        }
        int fib = 2;
        int prevFib = 1;

        for (int i = 2; i < nthTerm; i++) {
            int temp = fib;
            fib += prevFib;
            prevFib = temp;
        }
        return fib;
    }

    public static void main(String args[]) {
        int n = 40;


        long start = System.currentTimeMillis();
        System.out.println(n+"th term using recursion is: "+ recursiveFibbonacci(n));
        long stop = System.currentTimeMillis();
        System.out.println("Total Time take using recursion: " + (stop - start)  + " milliseconds");


        start = System.currentTimeMillis();
        System.out.println(n+"th term using iteration is: "+ iterativeFibbonacci(n));
        stop = System.currentTimeMillis();
        System.out.println("Total Time take using iteration: " + (stop - start)  + " seconds");
    }
}

Time Complexity using Recursion is exponential, and the big O is 2^n whereas the time complexity using iteration is of order n

Hence we can see for a larger number of n here in this case n = 40

the time taken to find the nth value will take 2^40 units of time whereas using iterative approach it will take only 40 units of time.

Hence time taken using recursion will always we greater than the time taken following iterative approach.

=============================================================================

thank you so much !!

please do thumbs up : )