Proszę wyjaśnić ten prosty kod:
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Jestem zdezorientowany z ostatnią linią, zwłaszcza, że jeśli na przykład n = 5, to zostanie wywołany fibonacci (4) + fibonacci (3) i tak dalej, ale nie rozumiem, jak ten algorytm oblicza wartość indeksu 5 przez to metoda. Proszę wyjaśnić szczegółowo!
Odpowiedzi:
W sekwencji Fibonacciego każda pozycja jest sumą dwóch poprzednich. Więc napisałeś algorytm rekurencyjny.
Więc,
Teraz już wiesz
fibonacci(1)==1 and fibonacci(0) == 0
. Możesz więc później obliczyć inne wartości.Teraz,
A z sekwencji Fibonacciego
0,1,1,2,3,5,8,13,21....
możemy zobaczyć, że dla5th element
sekwencji Fibonacciego powraca5
.Zobacz tutaj samouczek rekursji .
źródło
Z Twoim kodem są dwa problemy:
Kod
fibonacci(n - 1) + fibonacci(n - 2)
jest bardzo zły.
Problem w tym, że nazywa fibonacciego nie 50 razy, ale znacznie więcej.
Na początku nazywa się fibonacci (49) + fibonacci (48),
następnie fibonacci (48) + fibonacci (47) i fibonacci (47) + fibonacci (46)
.
Podejście do kodu nierekurencyjnego:
źródło
2*fibonacci(n+1)-1
, więc rośnie z taką samą złożonością jak same liczby Fibonacciego, czyli 1,618 ^ n zamiast 2 ^ nW pseudokodzie, gdzie n = 5, ma miejsce:
To dzieli się na:
To dzieli się na:
To dzieli się na:
To dzieli się na:
Skutkuje to: 5
Biorąc pod uwagę, że sekwencja Fibonnacciego to 1 1 2 3 5 8 ... , piątym elementem jest 5. Możesz użyć tej samej metodologii, aby znaleźć inne iteracje.
źródło
Rekursja może być czasami trudna do uchwycenia. Po prostu oceń to na kartce papieru na małą liczbę:
Nie jestem pewien, jak Java to ocenia, ale wynik będzie taki sam.
źródło
Możesz również uprościć swoją funkcję w następujący sposób:
źródło
Należy zauważyć, że ten algorytm jest wykładniczy, ponieważ nie przechowuje wyników wcześniej obliczonych liczb. np. F (n-3) jest wywoływane 3 razy.
Więcej szczegółów można znaleźć w algorytmie opracowanym przez dasgupta w rozdziale 0.2
źródło
Większość odpowiedzi jest dobra i wyjaśnia, jak działa rekurencja w Fibonacciego.
Oto analiza trzech technik, która obejmuje również rekursję:
Oto mój kod do przetestowania wszystkich trzech:
Oto wyniki:
Stąd widzimy, że memoizacja jest najlepsza pod względem czasu i ścisłego dopasowania pętli.
Jednak rekursja trwa najdłużej i być może powinieneś jej unikać w prawdziwym życiu. Również jeśli używasz rekurencji, upewnij się, że optymalizujesz rozwiązanie.
źródło
To najlepszy film, jaki znalazłem, w pełni wyjaśniający rekurencję i ciąg Fibonacciego w Javie.
http://www.youtube.com/watch?v=dsmBRUCzS7k
To jest jego kod sekwencji, a jego wyjaśnienie jest lepsze, niż mógłbym kiedykolwiek zrobić, próbując go wpisać.
źródło
W przypadku rozwiązania rekurencyjnego Fibonacciego ważne jest, aby zapisać wyniki mniejszych liczb Fibonacciego, podczas pobierania wartości większej liczby. Nazywa się to „zapamiętywaniem”.
Oto kod, który używa zapamiętywania mniejszych wartości Fibonacciego, podczas pobierania większej liczby Fibonacciego. Ten kod jest wydajny i nie wysyła wielu żądań tej samej funkcji.
źródło
w sekwencji Fibonacciego pierwsze dwie pozycje to 0 i 1, każda inna pozycja jest sumą dwóch poprzednich pozycji. to znaczy:
0 1 1 2 3 5 8 ...
więc piąta pozycja to suma czwartej i trzeciej pozycji.
źródło
Michael Goodrich i wsp. Dostarczają naprawdę sprytnego algorytmu w Strukturach Danych i Algorytmach w Javie, do rekurencyjnego rozwiązywania fibonacciego w czasie liniowym poprzez zwracanie tablicy [fib (n), fib (n-1)].
To daje fib (n) = fibGood (n) [0].
źródło
Oto rozwiązanie O (1):
Wzór na liczbę Fibonacciego Bineta użyty do powyższej implementacji. W przypadku dużych wejść
long
można zastąpićBigDecimal
.źródło
Sekwencja Fibbonacciego to taka, która sumuje wynik liczby po dodaniu do poprzedniego wyniku, zaczynając od 1.
Gdy zrozumiemy, czym jest Fibbonacci, możemy zacząć rozkładać kod.
Pierwsza instrukcja if sprawdza przypadek podstawowy, w którym może dojść do przerwania pętli. Poniższe oświadczenie else if robi to samo, ale można je przepisać w ten sposób ...
Teraz, gdy jest ustalony przypadek podstawowy, musimy zrozumieć stos wywołań. Twoje pierwsze wywołanie „fibonacci” będzie ostatnim, które zostanie rozstrzygnięte na stosie (sekwencja wywołań), ponieważ są one rozstrzygane w odwrotnej kolejności, z której zostały wywołane. Ostatnia wywoływana metoda jest najpierw rozwiązywana, potem ostatnia, która ma zostać wywołana przed nią i tak dalej ...
Tak więc wszystkie wywołania są wykonywane jako pierwsze, zanim cokolwiek zostanie „obliczone” na podstawie tych wyników. Przy wejściu 8 oczekujemy wyjścia 21 (patrz tabela powyżej).
Fibonacci (n - 1) jest wywoływana aż do przypadku podstawowego, a następnie Fibonacci (n - 2) jest wywoływana, aż osiągnie przypadek podstawowy. Kiedy stos zacznie sumować wynik w odwrotnej kolejności, wynik będzie taki ...
Ciągle bulgoczą (rozstrzygając wstecz) aż do momentu, gdy właściwa suma zostanie zwrócona do pierwszego sprawdzenia w stosie i w ten sposób otrzymasz odpowiedź.
Mimo to algorytm ten jest bardzo nieefektywny, ponieważ oblicza ten sam wynik dla każdej gałęzi, na którą dzieli się kod. Znacznie lepszym podejściem jest podejście „oddolne”, w którym nie jest wymagane zapamiętywanie (buforowanie) ani rekursja (głęboki stos wywołań).
Tak jak tak ...
źródło
Większość oferowanych tutaj rozwiązań działa w złożoności O (2 ^ n). Ponowne obliczanie identycznych węzłów w drzewie rekurencyjnym jest nieefektywne i powoduje marnowanie cykli procesora.
Możemy użyć zapamiętywania, aby funkcja Fibonacciego działała w czasie O (n)
Jeśli podążamy ścieżką programowania dynamicznego od dołu w górę, poniższy kod jest wystarczająco prosty, aby obliczyć fibonacciego:
źródło
Dlaczego ta odpowiedź jest inna
Każda inna odpowiedź:
(na marginesie: żadne z nich nie jest faktycznie wydajne; użyj wzoru Bineta, aby bezpośrednio obliczyć n- ty człon)
Ogon rekurencyjny Fib
Oto podejście rekurencyjne, które pozwala uniknąć podwójnego rekurencyjnego wywołania, przekazując zarówno poprzednią odpowiedź ORAZ poprzednią.
źródło
Jest to podstawowa sekwencja, która wyświetla lub uzyskuje wynik 1 1 2 3 5 8 jest to sekwencja, w której suma poprzedniej liczby zostanie wyświetlona jako następna.
Spróbuj obejrzeć link poniżej Samouczek dotyczący rekurencyjnej sekwencji Fibonacciego w Javie
Kliknij tutaj Obejrzyj samouczek dotyczący rekurencyjnej sekwencji Fibonacciego w języku Java dotyczący karmienia łyżeczką
źródło
Myślę, że to prosty sposób:
źródło
Odpowiedź RanRag (zaakceptowana) będzie działać dobrze, ale nie jest to zoptymalizowane rozwiązanie, dopóki nie zostanie zapamiętane, jak wyjaśniono w odpowiedzi Anila.
W przypadku rekurencyjnego rozważania poniżej wywołania metod
TestFibonacci
są minimalneźródło
źródło
Używając wewnętrznej ConcurrentHashMap, która teoretycznie mogłaby pozwolić tej rekurencyjnej implementacji na prawidłowe działanie w środowisku wielowątkowym, zaimplementowałem funkcję Fib, która używa zarówno BigInteger, jak i Recursion. Obliczenie pierwszych 100 liczb Fib zajmuje około 53 ms.
Kod testu to:
źródło
Oto jedna linia rekurencyjna febonacciego:
źródło
Spróbuj tego
źródło
Dla uzupełnienia, jeśli chcesz mieć możliwość obliczania większych liczb, powinieneś użyć BigInteger.
Przykład iteracyjny.
źródło
http://en.wikipedia.org/wiki/Fibonacci_number więcej szczegółów
Uczyń to tak prostym, jak to konieczne, bez potrzeby używania pętli while i innych pętli
źródło
źródło
Zastosowanie
while
:Zaletą tego rozwiązania jest to, że łatwo jest odczytać kod i go zrozumieć, mając nadzieję, że pomoże
źródło
Ciąg Fibbonacciego to taki, który sumuje wynik liczby, którą dodaliśmy do poprzedniego wyniku, powinniśmy zacząć od 1. Próbowałem znaleźć rozwiązanie oparte na algorytmie, więc budowałem kod rekurencyjny, zauważyłem, że zachowuję poprzedni numer i zmieniłem pozycję. Przeszukuję ciąg Fibbonacciego od 1 do 15.
źródło
źródło
Prosty Fibonacci
źródło
@chro jest na miejscu, ale nie pokazuje poprawnego sposobu, aby to zrobić rekurencyjnie. Oto rozwiązanie:
źródło