26

I've got two different methods, one is calculating Fibonacci sequence to the nth element by using iteration and the other one is doing the same thing using recursive method.

Program example looks like this:

import java.util.Scanner;

public class recursionVsIteration {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        //nth element input
        System.out.print("Enter the last element of Fibonacci sequence: ");
        int n = sc.nextInt();

        //Print out iteration method
        System.out.println("Fibonacci iteration:");
        long start = System.currentTimeMillis();
        System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibIteration(n));
        System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start);

        //Print out recursive method
        System.out.println("Fibonacci recursion:");
        start = System.currentTimeMillis();
        System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibRecursion(n));
        System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start);
    }

    //Iteration method
    static int fibIteration(int n) {
        int x = 0, y = 1, z = 1;
        for (int i = 0; i < n; i++) {
            x = y;
            y = z;
            z = x + y;
        }
        return x;
    }

    //Recursive method
    static int fibRecursion(int  n) {
        if ((n == 1) || (n == 0)) {
            return n;
        }
        return fibRecursion(n - 1) + fibRecursion(n - 2);
    }
}

I was trying to find out which method is faster. I came to the conclusion that recursion is faster for the smaller amount of numbers, but as the value of nth element increases recursion becomes slower and iteration becomes faster. Here are the three different results for three different n:

Example #1 (n = 10)

Enter the last element of Fibonacci sequence: 10
Fibonacci iteration:
Fibonacci sequence(element at index 10) = 55 
Time: 5 ms
Fibonacci recursion:
Fibonacci sequence(element at index 10) = 55 
Time: 0 ms

Example #2 (n = 20)

Enter the last element of Fibonacci sequence: 20
Fibonacci iteration:
Fibonacci sequence(element at index 20) = 6765 
Time: 4 ms
Fibonacci recursion:
Fibonacci sequence(element at index 20) = 6765 
Time: 2 ms

Example #3 (n = 30)

Enter the last element of Fibonacci sequence: 30
Fibonacci iteration:
Fibonacci sequence(element at index 30) = 832040
Time: 4 ms
Fibonacci recursion:
Fibonacci sequence(element at index 30) = 832040
Time: 15 ms

What I really want to know is why all of a sudden iteration became faster and recursion became slower. I'm sorry if I missed some obvious answer to this question, but I'm still new to the programming, I really don't understand what's going on behind that and I would like to know. Please provide a good explanation or point me in the right direction so I can find out the answer myself. Also, if this is not a good way to test which method is faster let me know and suggest me different method.

Thanks in advance!

msmolcic
  • 6,407
  • 8
  • 32
  • 56
  • 3
    Calling functions recursively adds overhead. – Robert Harvey Feb 11 '14 at 19:04
  • 1
    The two methods are **not** identical (even excluding recursion/iterative from the picture) – Justin Feb 11 '14 at 19:05
  • 6
    First problem: your method of benchmarking is massively flawed. You're really not doing enough work to measure the difference accurately. You should use `System.nanoTime`, and repeat the call several times so that you're measuring a useful amount of work. Next, look at the complexity of each call... Work out how much work is done in each case, as n grows. Hint: try walking through on paper what happens if you call fibRecursion(8) vs fibIteration(8). – Jon Skeet Feb 11 '14 at 19:05
  • The fastest method is the [closed form](http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio). – Elliott Frisch Feb 11 '14 at 19:21
  • A very good comparison of iterative vs recursive vs memoization implementations for Fibonacci series [here](https://stackoverflow.com/a/8532405/465053) – RBT Aug 10 '17 at 06:55
  • You may combine the recursion with local storage – Arefe Oct 27 '17 at 06:17

10 Answers10

19

For terseness, Let F(x) be the recursive Fibonacci 

F(10) = F(9)                      + F(8)
F(10) = F(8)        + F(7)        + F(7) + F(6)
F(10) = F(7) + F(6) + F(6) + F(5) + 4 more calls.
....

So your are calling F(8) twice, F(7) 3 times, F(6) 5 times, F(5) 7 times.. and so on

So with larger inputs, the tree gets bigger and bigger.

Chris Cudmore
  • 29,793
  • 12
  • 57
  • 94
  • 1
    Ok, it makes sense, could you also tell me why iteration becomes faster please? – msmolcic Feb 11 '14 at 19:16
  • Very simple, the loop will execute N times for Fib(N). But by the 3rd level of the recursion I did above, we've already called the function 14 times for N= 10, So even if a loop iteration cost exactly the same as a function call, we'd expect the loop to perform better at N = 10 (We still need to account for loop set up, which may account for the recursion being slightly fast for small N, but it's probably due to your method of timing which @JonSkeet mentioned above) – Chris Cudmore Feb 11 '14 at 19:20
  • Thanks everyone for replying, I think I got the main idea now, I liked your answer the most, thank you sir! – msmolcic Feb 11 '14 at 19:27
  • The reason for speed difference is: calling a function means putting the current function values and the call parameters on the stack, then after the function call finished the return value is put on the stack and the last calling function is loaded by loading its state from the stack and the returned value is read, too, to process it. These store and loads are memory accesses which are always slower than calculating inside CPU registers. Especially if reads are from outside CPU cache L1. Compare the CPU cycles for summation and cache reads: reads take 100+ cycles longer. – VisorZ Sep 30 '16 at 15:34
  • 1
    @visorz While what you say is true in a sense, it is actually incorrect in this particular context. It's the recursion on the same values over and over again that grows quickly, not the overhead of function calls. – Chris Cudmore Sep 30 '16 at 17:43
6

This article does a comparison between recursion and iteration and covers their application on generating fibonacci numbers.

As noted in the article,

The reason for the poor performance is heavy push-pop of the registers in the ill level of each recursive call.

which basically says there is more overhead in the recursive method.

Also, take a look at Memoization

starcodex
  • 2,198
  • 4
  • 22
  • 34
6

When doing the recursive implementation of Fibonacci algorithm, you are adding redundant calls by recomputing the same values over and over again.

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)

Notice, that fib(2) will be redundantly calculated both for fib(4) and for fib(3). However this can be overcome by a technique called Memoization, that improves the efficiency of recursive Fibonacci by storing the values, you have calculated once. Further calls of fib(x) for known values may be replaced by a simple lookup, eliminating the need for further recursive calls.

This is the main difference between the iterative and recursive approaches, if you are interested, there are also other, more efficient algorithms of calculating Fibonacci numbers.

Nayuki
  • 17,911
  • 6
  • 53
  • 80
Warlord
  • 2,798
  • 16
  • 21
4

Why is Recursion slower?

When you call your function again itself (as recursion) the compiler allocates new Activation Record (Just think as an ordinary Stack) for that new function. That stack is used to keep your states, variables, and addresses. Compiler creates a stack for each function and this creation process continues until the base case is reached. So, when the data size becomes larger, compiler needs large stack segment to calculate the whole process. Calculating and managing those Records is also counted during this process.

Also, in recursion, the stack segment is being raised during run-time. Compiler does not know how much memory will be occupied during compile time.

That is why if you don't handle your Base case properly, you will get StackOverflow exception :).

Ashishkumar Singh
  • 3,580
  • 1
  • 23
  • 41
Saiful Azad
  • 1,823
  • 3
  • 17
  • 27
2

Using recursion the way you have, the time complexity is O(fib(n)) which is very expensive. The iterative method is O(n) This doesn't show because a) your tests are very short, the code won't even be compiled b) you used very small numbers.

Both examples will become faster the more you run them. Once a loop or method has been called 10,000 times, it should be compiled to native code.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
2

If anyone is interested in an iterative Function with array:

public static void fibonacci(int y)
{
    int[] a = new int[y+1];
    a[0] = 0;
    a[1] = 1;
    System.out.println("Step 0: 0");
    System.out.println("Step 1: 1");
    for(int i=2; i<=y; i++){
        a[i] = a[i-1] + a[i-2];
        System.out.println("Step "+i+": "+a[i]);
    }
    System.out.println("Array size --> "+a.length);
}

This solution crashes for input value 0.

Reason: The array a will be initialized 0+1=1 but the consecutive assignment of a[1] will result in an index out of bounds exception.

Either add an if statement that returns 0 on y=0 or initialize the array by y+2, which will waste 1 int but still be of constant space and not change big O.

igr
  • 10,199
  • 13
  • 65
  • 111
Alan Meile
  • 120
  • 1
  • 4
2

I prefer using a mathematical solution using the golden number. enjoy

private static final double GOLDEN_NUMBER = 1.618d;

public long fibonacci(int n) {
    double sqrt = Math.sqrt(5);

    double result = Math.pow(GOLDEN_NUMBER, n);

    result = result - Math.pow(1d - GOLDEN_NUMBER, n);

    result = Math.round(result / sqrt);

    return Double.valueOf(result).longValue();
}
Aldo Infanzon
  • 46
  • 6
2

Whenever you are looking for time taken to complete a particular algorithm, it's best you always go for time complexity.

Evaluate the time complexity on the paper in terms of O(something).

Comparing the above two approaches, time complexity of iterative approach is O(n) whereas that of recursive approach is O(2^n).

Let's try to find the time complexity of fib(4)

Iterative approach, the loop evaluates 4 times, so it's time complexity is O(n).

Recursive approach,

                               fib(4)

             fib(3)              +               fib(2)

      fib(2)   +    fib(1)           fib(1)     +       fib(0)

fib(1)  +  fib(0)

so fib() is called 9 times which is slightly lower than 2^n when the value of n is large, even small also(remember that BigOh(O) takes care of upper bound) .

As a result we can say that the iterative approach is evaluating in polynomial time, whereas recursive one is evaluating in exponential time

Varunnuevothoughts
  • 61
  • 2
1

The recursive approach that you use is not efficient. I would suggest you use tail recursion. In contrast to your approach tail recursion keeps only one function call in the stack at any point in time.

public static int tailFib(int n) {
    if (n <= 1) {
        return n;
    }
    return tailFib(0, 1, n);
}

private static int tailFib(int a, int b, int count) {
    if(count <= 0) {
        return a;
    }
    return tailFib(b, a+b, count-1);
}

public static void main(String[] args)  throws Exception{
    for (int i = 0; i <10; i++){
        System.out.println(tailFib(i));
    }
}
gorros
  • 1,411
  • 1
  • 18
  • 29
1

I have a recursive solution that you where the computed values are stored to avoid the further unnecessary computations. The code is provided below, 

public static int fibonacci(int n) {

        if(n <=  0) return 0;
        if(n == 1) return 1;

        int[] arr = new int[n+1];

        // this is faster than using Array
        // List<Integer> lis = new ArrayList<>(Collections.nCopies(n+1, 0));

        arr[0] = 0;
        arr[1] = 1; 

        return fiboHelper(n, arr);
    }

    public static int fiboHelper(int n, int[] arr){

        if(n <= 0) {
            return arr[0];
        }

        else if(n == 1) {
            return arr[1];
        }

        else {

            if( arr[n-1] != 0 && (arr[n-2] != 0 || (arr[n-2] == 0 && n-2 == 0))){    
                return arr[n] = arr[n-1] + arr[n-2]; 
            }

            else if (arr[n-1] == 0 && arr[n-2] != 0 ){
                return arr[n] = fiboHelper(n-1, arr) + arr[n-2]; 
            }

            else {
                return  arr[n] = fiboHelper(n-2, arr) + fiboHelper(n-1, arr );
            } 

        }             
    }
Arefe
  • 11,321
  • 18
  • 114
  • 168