Ciąg Fibonacciego
Ciąg Fibonacciego:
zaczyna się od 0 i 1, a każdy następny element ciągu ma wartość stanowiącą sumę dwóch poprzednich elementów. Takie ciągi występują w naturze pod postacią spiral. Współczynnik wartości kolejnych elementów ciągu Finonacciego zbiega się do stałej wartości 1,618…, nazywanej czasem złotym podziałem. Ludzie uważają kształty wykorzystujące złoty podział za szczególnie estetyczne. Architekci często projektują okna, pomieszczenia i budynki tak, aby miały właśnie taki stosunek szerokości i długości. Kartki pocztowe również często mają ten stosunek szerokości do wysokości.
Ciąg Fibonacciego można zdefiniować rekurencyjnie w następujący sposób:
fibonacci(1) = 1
fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)
Istnieją dwa przypadki bazowe: fibonacci(0) powoduje zwrócenie wartości 0, a fibonacci(1) zwrócenie wartości 1. Rysunek 18.5 przedstawia rekurencyjne wyliczenie i-tego elementu ciągu Fibonacciego za pomocą metody fibonacci (wiersze od 9. do 18.). Metoda main (wiersze od 20. do 26.) testuje fibonacci, wyświetlając elementy ciągu od 0. do 40. Zmienna counter utworzona w nagłówku pętli for (wiersz 22.) wskazuje, który element ciągu obliczać w poszczególnych iteracjach pętli. Wartości ciągu bardzo szybko przyrastają (choć nie tak szybko jak dla silni). Dlatego korzystamy z typu BigInteger jako typu parametru i zwracanej
wartości w metodzie fibonacci.
Wywołanie metody fibonacci (wiersz 24.) w metodzie main nie jest wywołaniem rekurencyjnym, ale wszystkie następne wywołania metody fibonacci wykonywane z wierszy 15. i 16. są wywołaniami rekurencyjnymi, ponieważ metoda fibonacci wywołuje samą siebie. W każdym wywołaniu fibonacci od razu dochodzi do testowania przypadków bazowych — wartości 0 lub 1 w number
(wiersze 10. i 11.). Jeśli warunek z wierszy 10. i 11. jest prawdziwy, fibonacci po prostu zwraca number, bo fibonacci(0) to 0 i fibonacci(1) to 1. Co istotne, jeśli number jest większe od 1, krok rekurencyjny generuje dwa wywołania rekurencyjne (wiersze 15. i 16.), każde z nieco mniejszym problemem niż oryginał. Wiersze 15. i 16. używają metod add i subtract z BigInteger, aby wspomóc implementację kroku rekurencyjnego. Wykorzystujemy również stałą typu BigInteger o nazwie TWO zdefiniowaną w wierszu 6.
2 // Rekurencyjna metoda wyliczania elementów ciągu Fibonacciego
3 import java.math.BigInteger;
4
5 public class FibonacciCalculator {
6 private static BigInteger TWO = BigInteger.valueOf(2);
7
8 // Rekurencyjna deklaracja metody fibonacci
9 public static BigInteger fibonacci(BigInteger number) {
10 if (number.equals(BigInteger.ZERO) ||
11 number.equals(BigInteger.ONE)) { // Przypadki bazowe
12 return number;
13 }
14 else { // Krok rekurencyjny
15 return fibonacci(number.subtract(BigInteger.ONE)).add(
16 fibonacci(number.subtract(TWO)));
17 }
18 }
19
20 public static void main(String[] args) {
21 // Wyświetlenie wartości ciągu Fibonacciego dla elementów od 0. do 40.
22 for (int counter = 0; counter <= 40; counter++) {
23 System.out.printf("Element %d. ciągu Fibonacciego to: %d%n", counter,
24 fibonacci(BigInteger.valueOf(counter)));
25 }
26 }
27 }
Element 0. ciągu Fibonacciego to: 0
Element 1. ciągu Fibonacciego to: 1
Element 2. ciągu Fibonacciego to: 1
Element 3. ciągu Fibonacciego to: 2
Element 4. ciągu Fibonacciego to: 3
Element 5. ciągu Fibonacciego to: 5
Element 6. ciągu Fibonacciego to: 8
Element 7. ciągu Fibonacciego to: 13
Element 8. ciągu Fibonacciego to: 21
Element 9. ciągu Fibonacciego to: 34
Element 10. ciągu Fibonacciego to: 55
...
Element 37. ciągu Fibonacciego to: 24157817
Element 38. ciągu Fibonacciego to: 39088169
Element 39. ciągu Fibonacciego to: 63245986
Element 40. ciągu Fibonacciego to: 102334155
Rysunek 18.5. Rekurencyjna metoda wyliczania elementów ciągu Fibonacciego
Analiza wywołań metody fibonacci
Rysunek 18.6 przedstawia sposób wyliczania przed kod wartości metody fibonacci(3). U dołu rysunku otrzymujemy wartości 1, 0 i 1 — są to wyniki wyliczania przypadków bazowych. Dwie pierwsze zwracane wartości (od lewej do prawej) — 1 i 0 — są efektem wywołania metod fibonacci(1) i fibonacci(0). Suma 1 i 0 jest zwracana jako wynik fibonacci(2). Jest ona dodawana do wyniku
(1) wywołania fibonacci(1), dając wartość 2. Końcowa wartość jest zwracana jako wartość fibonacci(3).
Rysunek 18.6. Zbiór wywołań rekurencyjnych przy wyliczaniu fibonacci(3)
Rysunek 18.6 podnosi pewne interesujące pytania w kwestii kolejności, w której kompilator Javy wylicza operandy operatorów. Kolejność jest inna niż ta, w której operatory są stosowane dla operandów (czyli zasady kolejności wykonywania działań). Z rysunku 18.6 wnioskujemy, że wywołanie fibonacci(3) powoduje dwa wywołania rekurencyjne: fibonacci(2) i fibonacci(1). W jakiej kolejności
zostaną wykonane? Java wskazuje, że kolejność wykonywania działań odbywa się od lewej do prawej. Oznacza to, że najpierw dojdzie do wywołania fibonacci(2), a dopiero później fibonacci(1).
Kwestie złożoności
Warto ostrzec przed programami rekurencyjnymi, które generują wartości w sposób podobny jak tu liczby Fibonacciego. Każde wywołanie metody fibonacci, które nie odpowiada jednej z klas bazowych (0 lub 1), owocuje dwoma kolejnymi wywołaniami rekurencyjnymi metody fibonacci. Obliczenie 20. elementu ciągu od kodu z rysunku 18.5 wymaga 21 891 wywołań metody fibonacci, ale obliczenie 30. elementu wymaga już 2 692 537 wywołań! Zauważ, że każde zwiększenie wartości powodowało znaczące spowolnienie działania i dłuższy czas oczekiwania na wynik. Dla 31. elementu wywołań metod jest już 4 356 617,
a dla 32. aż 7 049 155. Liczba wywołań między elementami od 30. do 31. zwiększyła się o 1 664 080, a między 31. i 32. aż o 2 692 538. Liczba wywołań między sąsiednimi elementami zwiększyła się aż o półtora raza. Problemy tej natury mogą rozłożyć na łopatki nawet najbardziej potężne komputery.
(Uwaga: Teoria złożoności pozwala naukowcom określać, jak mocno muszą pracować algorytmy, aby wykonać swoje zadania. Kwestie złożoności są najczęściej wykładane na kursach dotyczących algorytmów i struktur danych.)
Wskazówka poprawiająca wydajność
Unikaj rekurencyjnych programów podobnych do ciągu Fibonacciego, ponieważ powodują one wykładniczą eksplozję wywołań metod.
Programowanie w Javie. Solidna wiedza w praktyce. Wydanie XI, Autorzy: Paul Deitel, Harvey Deitel, Wydawnictwo: Helion
