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()).

pokaż źródło

drukujpomoc

01.// wykorzystujemy klasę Scanner z pakietu java.util

02.import java.util.*;

03. 

04./**

05. * N-ty element ciągu Fibonacciego rekurencyjnie i iteracyjnie

06. * @author kodatnik.blogspot.com

07. */

08.public class CiagFibonacciego {

09.  

10. // metoda zwraca n-ty element ciągu Fibonacciego

11. // wersja rekurencyjna

12. public static int fibR(int n) {

13.   

14.  if (n < 2) return n; // jeśli n<2 zwracamy n (dla zera 0 dla jedynki 1)

15.   

16.  return fibR(n-1) + fibR(n-2); // jeśli nie to zwracamy sumę elementu poprzedniego i jeszcze wcześniejszego

17. }

18.  

19. // metoda zwraca n-ty element ciągu Fibonacciego

20. // wersja iteracyjna 

21. public static int fibI(int n) {

22.  int elementA = 0; // zmienne pomocnicze symbolizujące

23.  int elementB = 1; // element poprzedni B i jeszcze wcześniejszy A

24.   

25.  int wynik = 0; // zmienna wynik, pod którą podstawimy obliczoną wartość

26.   

27.  if (n < 2) return n; // jeśli n<2 zwracamy n (dla zera 0 dla jedynki 1)

28.    

29.   // jeśli nie to liczymy n=ty element ciagu

30.   for(int i = 2; i <= n; i++){

31.    wynik = elementA + elementB; // pod wynik podstawiamy sumę poprzednich elementów

32.    elementA = elementB; // modyfikujemy zmienne przechowujące

33.    elementB = wynik;  // dwie ostatnie wartości

34.   }

35.   

36.  return wynik; // zwracamy wynik

37. }

38.  

39. public static void main(String[] args) {

40.   

41.  Scanner sc = new Scanner(System.in);

42.  System.out.print ("Który element ciągu Fibonacciego chcesz obliczyć: " );

43. 

44.  // pobieramy od użytkownika liczbę

45.  int n = sc.nextInt();

46. 

47.  // wyświetlamy na ekranie obliczony element

48.  System.out.println( n + "-ty element ciągu Fibonacciego (rekurencja) wynosi: " + fibR(n));

49.  System.out.println( n + "-ty element ciągu Fibonacciego (iteracja) wynosi: " + fibI(n)); 

50.  

51. }

52.}

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ń.