Ciąg Fibonacciego rekurencyjnie i iteracyjnie

Ciąg Fibonacciego to ciąg liczb naturalnych określony wzorem f(n)=f(n-1)+f(n-2) dla danych f(0)=0 i f(1)=1. Chcemy napisać metodę obliczającą n-ty wyraz tego ciągu. Zastosujemy rozwiązanie rekurencyjne (metoda fibR()) oraz iteracyjne (metoda fibI()).

// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * N-ty element ciągu Fibonacciego rekurencyjnie i iteracyjnie
 * @author kodatnik.blogspot.com 
 */ 
public class CiagFibonacciego {
 
 // metoda zwraca n-ty element ciągu Fibonacciego
 // wersja rekurencyjna 
 public static int fibR(int n) {
  
  if (n < 2) return n; // jeśli n<2 zwracamy n (dla zera 0 dla jedynki 1)
  
  return fibR(n-1) + fibR(n-2); // jeśli nie to zwracamy sumę elementu poprzedniego i jeszcze wcześniejszego
 }
 
 // metoda zwraca n-ty element ciągu Fibonacciego
 // wersja iteracyjna  
 public static int fibI(int n) {
  int elementA = 0; // zmienne pomocnicze symbolizujące
  int elementB = 1; // element poprzedni B i jeszcze wcześniejszy A
  
  int wynik = 0; // zmienna wynik, pod którą podstawimy obliczoną wartość
  
  if (n < 2) return n; // jeśli n<2 zwracamy n (dla zera 0 dla jedynki 1)
   
   // jeśli nie to liczymy n=ty element ciagu
   for(int i = 2; i <= n; i++){ 
    wynik = elementA + elementB; // pod wynik podstawiamy sumę poprzednich elementów
    elementA = elementB; // modyfikujemy zmienne przechowujące
    elementB = wynik;  // dwie ostatnie wartości
   }
  
  return wynik; // zwracamy wynik
 }
 
 public static void main(String[] args) {
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Który element ciągu Fibonacciego chcesz obliczyć: " );

  // pobieramy od użytkownika liczbę
  int n = sc.nextInt();

  // wyświetlamy na ekranie obliczony element
  System.out.println( n + "-ty element ciągu Fibonacciego (rekurencja) wynosi: " + fibR(n));
  System.out.println( n + "-ty element ciągu Fibonacciego (iteracja) wynosi: " + fibI(n));  
 
 }
}

Uruchomiona aplikacja:

Który element ciągu Fibonacciego chcesz obliczyć: 10
10-ty element ciągu Fibonacciego (rekurencja) wynosi: 55
10-ty element ciągu Fibonacciego (iteracja) wynosi: 55

Rozwiązanie rekurencyjne jest bardzo kosztowne. Sprawdź czas wykonania jednej i drugiej metody dla dużych n, bądź też liczbę rekurencyjnych wywołań potrzebnych do takich obliczeń.