Zrozumienie rekurencji za pomocą serii Fibonacci

Question

Próbuję lepiej zrozumieć rekurencję i działanie instrukcji return. W związku z tym patrzę na fragment kodu służący do identyfikacji numeru fibonacci związanego z danym terminem - w tym przypadku 4. Mam trudności ze zrozumieniem instrukcji else.

def f(n): 
    if n == 0: 
    return 0 
    if n == 1: 
    return 1 
    else: 
    return f(n-1) + f(n-2) 

f(4) 

Próbowałem, używając Wizualizacja Python aby zbadać, co dzieje się na każdym kroku, ale gubię gdy trafi oświadczenie innego.

Wygląda na to, że przyjmuje wartość n i odejmuje 1, aby utworzyć nową wartość n równą 3, która powraca do definicji funkcji. Wygląda więc na to, że zwraca wartość tylko z pierwszej funkcji w instrukcji else. Jednakże instrukcja else jest napisana w celu zwrócenia sumy 2 funkcji f (n-1) + f (n-2), w którym to przypadku myślę, że wartość zwracana wynosiłaby 5? Czy możesz dodać 2 funkcje jednocześnie?

Z góry dziękuję za pomoc.

Tu jest link do kodu w Pythonie Visualize Sum of 2 functions

Answer 1

W przypadku wątpliwości, po prostu rozbicie go.

przepływ drzewo jest rzeczywiście intuicyjne do rzeczywistej kontroli przepływu, ale po zrozumieniu sekwencji połączeń, staje się jaśniejsze. Rzeczą zrozumiałą jest to, że dzielisz większe obliczenia na sumę mniejszych obliczeń, a zatrzymujesz się, gdy trafisz w bazę (instrukcje if). Teraz możesz przeprowadzić wszystkie małe obliczenia i połączyć wyniki tych małych obliczeń, aby uzyskać większy, większy wynik, aż uzyskasz ostateczną odpowiedź.

Za każdym razem, gdy wywołanie rekurencyjne trafi w podstawową obudowę, zwróci wartość 1 lub 0 w zależności od przypadku. Ta wartość zostanie zwrócona do poprzedniego rozmówcy. Aby zrozumieć, należy rozważyć:

f(1)3 + f(0)3

tu zauważyć, że indeks reprezentuje głębokość drzewa połączeń rekurencji. Połączenie zostanie wykonane przez f(2)2. f(1)3 jest obliczana jako pierwsza, a 1 jest zwracana do f(2)2. f(0)3 jest następnie obliczana, a 0 jest zwracana do. Dwie zwracane wartości są sumowane, a wynikiem jest 1.

f(2)2 następnie powraca1 aby ktokolwiek go nazywa , która w tym przypadku dzieje się f(3)1. f(3)1 o nazwie f(2)2 + f(1)2, tymczasem ten inny f(1)2 również zwraca 1 do f(3)1, który teraz dodaje to z wynikiem f(2)2, tworząc 2.

f(3)1 teraz przechodzi 2 do f(4)0, jego rozmówca, który się zadzwonić f(3)1 + f(2)1 ... i tak to idzie.

---

Alternatywnym sposobem patrzenia na to, aby rozpocząć od pierwszego wywołania funkcji, która jest faktycznie wykonane: f(4)0.

f(4)0 oblicza f(3)1 + f(2)1. Ale aby obliczyć f(3)1, musi on znać f(2)2 + f(1)2, i podobnie, aby obliczyć f(2)1, musi znać f(1)2 + f(0)2 i tak dalej.

Answer 2

Dodanie kilku sprawozdań z tuszem może również pomóc w wyjaśnieniu sekwencję:

def f(n): 
    print("Number received:", n) 
    if n == 0: 
     return 0 
    if n == 1: 
     return 1 
    else: 
     print("---- First recursion ----") 
     a = f(n-1) 
     print("---- Second recursion ----") 
     b = f(n-2) 
     print(" a=:",a,"; b=",b,"; returning:", a+b) 
     return a + b 

print("Final f(4)=", f(4)) 

wyjściowa:

Number received: 4 
---- First recursion ---- 
Number received: 3 
---- First recursion ---- 
Number received: 2 
---- First recursion ---- 
Number received: 1 
---- Second recursion ---- 
Number received: 0 
a=: 1 ; b= 0 ; returning: 1 
---- Second recursion ---- 
Number received: 1 
a=: 1 ; b= 1 ; returning: 2 
---- Second recursion ---- 
Number received: 2 
---- First recursion ---- 
Number received: 1 
---- Second recursion ---- 
Number received: 0 
a=: 1 ; b= 0 ; returning: 1 
a=: 2 ; b= 1 ; returning: 3 
Final f(4)= 3