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", 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!

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.