java - Recursion vs. Iteration (Fibonacci sequence)

Question

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, fibIteration(n));
        System.out.printf("Time: %d ms
", 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, fibRecursion(n));
        System.out.printf("Time: %d ms
", 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!

Answer 1

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.