Tip:
Highlight text to annotate it
X
Tym wideo chcę osiągnąć,
żebyśmy zrozumieli, co sie naprawdę dzieje,
gdy odwołujemy się do naszej rekurencyjnej funkcji.
Zakładam, że ktoś wywołuje ją
i wpisuje 5 jako argument.
Nie chcę wybrać zbyt dużej liczby,
gdyż wtedy będę tłumaczył w nieskończoność.
Wypróbujmy fibonacci(5)
W tym przypadku, wynikając z kontekstu funkcji,
parametr n przyjmie tu wartość 5
więc przy pierwszym przejściu, parametr n będzie się równał 5
Z zapisu funkcji wynika, że
gdy n jest mniejsze od 2, to zwróci nam n.
5 na pewno nie jest mniejsze od 2
więc przechodzimy do alternatywnej części operacji if
a więc operacja else, która nam zwraca
fibonacci z (n-1) plus fibonacci z (n-2)
więc gdy to wywołam, to zredukuje się to do,
gdy chcecie to sobie w ten sposób wyobrazić, albo łatwiej to określając,
zwróciłaby, to samo co wynik fibonacci z
pamiętajcie, że n to 5
więc n-1 to 4
plus fibonacci z n-2; gdy wystartowaliśmy funkcje n równało się 5
a 5-2 to 3
to są po prostu dalsze wywołania funkcji
więc przechodzimy to jeszcze raz
n nie jest 5, lecz 4 i 3
wypróbujmy to
tutaj n równa się 4
n ma wartość 4
znowu 4 nie jest mniejsze od 2
więc nie robimy tej części
przechodzimy do operacji else
obliczamy fibonacci(4-1), a więc z 3
to się skraca do,
albo raczej powiedziałbym, że roskłada się
na finonacci z 4-1, co się równa 3
plus fibonacci z 4-2
co jest fibonacci z 2
więc to tutaj w sumie na zwóci to tutaj
a to po prawej zwróci nam fibonacci z 3
zaznaczę to, bo zaraz pomieszają nam się
więc to nam zwróci to w magencie
a to, co podkreśliłem na zielono zwróci nam
n teraz równa się 3, 3 nie jest mniejsze od 2
więc przechodzimy tu
i to nam zwróci fibonacci z 3-1, co jest fibonacci(2)
i plus fibonacci z 3-2, co jest fibonacci (1)
potem przechodzimy tutaj
a teraz musimy obliczyć to wszystko
a to są po prostu dalsze odwołania do funkcji fibonacci
i fibonacci z 3, widzicie jakie zawiłe to się staje
zacznę pisać skrót fib, zamiast fibonacci
żeby mi się miejsce nie skończyło
fibonacci z 3. Gdy to wywołujemy
n 3 nie jest mniejsze od 2
to się rozkłada do fibonacci z 3-1
napiszę fib, zamiast fibonacci
fibonacci z 2 plus fibonacci z 3-2
plus fibonacci z 1
więc to skraca albo rozkłada się do tego
a tutaj fibonacci z 2
2 nie jest mniejsze od 2
więc otrzymamy fibonacci z 2-1
fibonacci z 1 plus fibonacci z 2-2
a więc fibonacci z 0
więc to się rozkłada na te dwa odwołania funkcji fibonacci
a tutaj to samo z fibonacci z 2
odwołaliśmy się do fibonacci z 2
to się rozkłada dokładnie jak fibonacci z 2
rozłoży się do wywołania
fibonacci z 1 i fibonacci z 0
a potem mamy fibonacci z 1
to jest interesujące
ponieważ, gdy n równa się 1
to ta operacja tu nagle staje się istotna
gdyż n jest mniejsze od 2 i tutaj jest napisane "zwrócic n"
więc to tutaj upraszcza się
to wyrażenie upraszcza się do 1
zwraca nam 1
A potem przyglądamy się tym wszystkim tutaj
fibonacci z 2; wiemy, że fibonacci z 2 równa się fibonacci z 1 plus fibonacci z 0
pozwólcie mi to tu napisać
więc tutaj jest fibonacci z 1 plus fibonacci z 0
fib jest skrótem dla fibonacci
a potem znamy fibonacci z 1
1 jest mniejsze od 2, więc zwraca nam n
więc to zwróci nam 1
fibonacci z 1 po prostu zwraca nam 1
fibonacci z 0
a 0 jest mniejsze od 2, zwraca nam 0
więc fibonacci z 0 tylko zwraca 0
fibonacci z 0 zwraca 0
fibonacci z 1 zwraca 1
fibonacci z 0 zwraca 0
a następnie fibonacci z 1 zwraca 1
fibonacci z 0 zwraca 0
więc cały czas interpreter wykonuje to wywołanie rekurencyjnej funkcji
musi zapamiętać wszystkie wcześniejsze wyniki, przez które tu dotarł
gdyż gdy wreszcie przejdzie do tych podstawowych przypadków
gdy przejdzie do n=1 albo 0
to wreszcie dostaje liczbę jako wynik
potem musi złożyć to do wcześniejszego wyniku
więc fibonacci z 2 tutaj
jest 1+0
fibonacci z 2 skróci nam się do 1
Fibonacci z 3 jest fibonacci z 2+ fivonacci z 1
te się skrócą do 1
więc to równa się 1+1
więc to będzie się równało 2
przechodzimy tu do fibonacci z 2
fibonacci z 1 + fibonacci z 0 =1
fibonacci z 2
1+0 to 1
idziemy dalej do fibonacci z , to jest 1
A teraz wchodzimy do tego poziomu
w sumie to odbudujemy to, aż odzyskamy nasze pierwotne odwołanie funkcji
i nie wyjaśnię dokładnie
jak interpreter to dokładnie robi
gdyż to jest fascynujące przedystkutowanie
ale tylko myślę jak zrozumiemy, co się dzieje
podczas odwołania do tej rekurencyjnej funkcji i dlaczego, dlaczego to działa
dlaczego daję nam prawidłową odpowiedź
A następnie przechodzimy tu do fibonacci z 4
fibonacci z 4, czwarta liczba fibonacciego
jest sumą 3 i 2 liczby fibonacciego
które już wyliczyliśmy
mamy 2 i 1, po prostu sumujemy i otrzymujemy 3
3 liczba fibonacciego, z definicji ciąfu fibonacciego
jest sumą pierwszej i drugiej liczby
te równają się 1
suma 1 plus 1 to 2
piąta liczby fibonacciego
piąta liczba fibonacciego
jest sumą czwartej i trzeciej
te równają się 3 i 2
więc 3 plus 2 to 5
więc to tutaj równa się 5
Mam nadzieję, że to trochę wyjaśnia
jak ten rekurencyjny program naprawdę działa
ciekawe jest
że gdybyśmy nie poszli na dół i nie określilibyśmy
podstawowych przypadków fibonacci z 1 i fibonacci z 0
po prostu wywoływałoby się w nieskończoność i nigdy by do nieczego nie doszło
i elementarnym składnikiem rekurencji jest to, że może się sama do siebie odwoływać
i za każdym razem, gdy się sama wywołuje
schodzi do podstawowych przypadków
więc w pewnym momencie
gdy się nadal wywołuję, gdy się nadal wywołuję
wreszcie będzie w stanie rozłożyć te wywołania
żeby przejść to podstawowych przypadow
a potem zrekonstruować z tego co było pierwotną wartością
i dlatego to funkcjonuję
każde wywołanie funkcji fibonacci jest prostszą wersją
Mamy mniejsze n
i wreszcie nasz n dotrze do podstawowych przypadków
które mi dadzą rzeczywiste wartości
które mogę potem wyliczyć dla naszych wcześniejszych wywołań
mam nadzieję, że to pomogło wam trochę
rekurencja może być myląca
ale zarazem
może też być eleganckie i piękne w swój własny sposób