Ciąg Fibonacciego w Javie

Ewa Klimowicz

10 sierpnia, 2023

3 min

• Specjalizacja
• Java

Ostatnia aktualizacja 10 sierpnia, 2023

W matematyce ciąg Fibonacciego to ciąg liczb naturalnych, zaczynający się od 0 i 1, w którym każda kolejna liczba jest sumą dwóch poprzednich. Wiele matematycznych konceptów ma swoje zastosowanie w programowaniu i nie inaczej jest w tym przypadku. Ciąg Fibonacciego w Javie często jest używany do nauki podstaw algorytmów i rekurencji.

Sprawdź: Składnia Pythona – przegląd podstawowych elementów

Ciąg Fibonacciego – Java

Implementacja iteracyjna

Jednym ze sposobów obliczenia ciągu Fibonacciego jest użycie pętli. Można to zrobić za pomocą następującego kodu:

public static int fibonacci(int n) {
  int a = 0, b = 1, suma;
  for(int i = 2; i <= n; i++) {
    suma = a + b;
    a = b;
    b = suma;
  }
  return b;
}

Co się dzieje w poszczególnych częściach kodu?

• Deklaracja zmiennych: Trzy zmienne a, b, i suma są zadeklarowane i zainicjalizowane. a i b są pierwszymi dwoma liczbami w ciągu Fibonacciego, a suma będzie używana do przechowywania sumy dwóch poprzednich liczb w ciągu.
• Pętla for: Pętla zaczyna się od i = 2, ponieważ pierwsze dwie liczby w ciągu Fibonacciego już zdefiniowano (a = 0, b = 1). Pętla będzie się wykonywała, dopóki i jest mniejsze lub równe n, gdzie n to numer liczby, którą chcemy obliczyć w ciągu Fibonacciego.
• Ciało Pętli: W ciele pętli trzy operacje wykonują się w każdej iteracji:
  • suma oblicza się jako suma a i b, czyli dwóch ostatnich liczb w ciągu.
  • a następnie ustawia się na wartość b.
  • b ustawia się na wartość suma. W ten sposób, a i b zawsze przechowują dwie ostatnie liczby w ciągu.
• Zwracanie wyniku: Po zakończeniu pętli, zwracana jest wartość b, która jest żądaną liczbą w ciągu Fibonacciego.

Przykładowo, jeśli wywołasz fibonacci(5), kod zwróci wartość 5, która jest piątą liczbą w ciągu Fibonacciego.

Dalsza część tekstu znajduje się pod materiałem wideo:

Implementacja rekurencyjna

Ciąg Fibonacciego (Java) można także obliczyć rekurencyjnie:

public static int fibonacci(int n) {
  if (n <= 1) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}

Co to oznacza?

• Warunek bazowy: Jeśli n jest mniejsze lub równe 1, funkcja zwraca wartość n. Jest to warunek bazowy rekurencji, który odpowiada za zakończenie rekurencyjnych wywołań. Dla n = 0 zwraca 0, a dla n = 1 zwraca 1, co są dwoma pierwszymi liczbami w ciągu Fibonacciego.
• Wywołanie rekurencyjne: Jeśli n jest większe niż 1, funkcja zwraca sumę dwóch rekurencyjnych wywołań: fibonacci(n-1) i fibonacci(n-2). Te wywołania odpowiadają dwóm poprzednim liczbom w ciągu Fibonacciego.

Rekurencyjna natura tej funkcji prowadzi do tego, że tworzy ona strukturę drzewa wywołań, gdzie każde wywołanie prowadzi do dwóch dalszych wywołań (dopóki nie osiągniemy warunku bazowego).

Chociaż ten kod cechuje się łatwością zrozumienia, jest on mniej wydajny niż iteracyjna wersja, ponieważ wiele wywołań rekurencyjnych oblicza te same wartości wielokrotnie. Dla większych wartości n, może to prowadzić do znacznego spowolnienia.

Czytaj także:

Ciąg Fibonacciego – właściwości i zastosowania złotej proporcji

Java enum – wprowadzenie do typów wyliczeniowych