Jak działa rekurencja?

0

Cześć,

Mam pytanie jak działa taka funkcja:

function f(n) {
    if (n == 0) { return 0; }
    if (n == 1) { return 1; }

    return f(n - 1) + f(n - 2);
}

console.log(f(6));

Rozumiem, ze rekurencja polega na ponownym wywoływaniu się funkcji dopóki określony warunek jest spełniony. Jak określana jest wartość return f(n-1) + f(n -2) ? f(n-1) i f(n-2) wywołują ponownie funkcję i w tym przypadku byłoby to:

f(6) = f(6-1) => f(5) = f(5-1) => f(4) = f(4-1) => f(3) = f(3-1) => f(2) = f(2-1) = 1
f(6) = f(6-2) => f(4) = f(4-2) => f(2) = f(2-2) = 0

Gdzie jest błąd w moim rozumieniu działania tej funkcji? Co zwraca każde wywołanie poza kolejnym wywołaniem funkcji? Prosiłbym o łopatologiczne wyjaśnienie tematu.

EDIT
Ok, już to rozgryzłem. Może komuś się przyda. Polecam zamienić zwracane wartości na stringi i przyjrzeć się dokładnie temu co jest zwracane :)

    if (n == 0) { return "0"; }
    if (n == 1) { return "1"; }

    result: 1011010110110

Pozdrawiam

3

Nie wyjaśnię ci tego na forum bo to długi temat ale jest dwie dobre książki, które ci to wytłumaczą:
„Asembler – sztuka programowania” (rozdział 5).
„Kompilatory. Reguły, metody i narzędzia” – w tej książce jest specjalny rozdział na ten temat.
W pierwszej kolejności musisz sobie uświadomić, że każde wywołanie funkcji tworzy na stosie tzw. ramkę (ang. stack frame), która zawiera lokalne kopie zmienny oraz adres powrotu do miejsca, z którego funkcja została wywołana….

2

Tu: https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2 Masz dobrze wytłumaczoną rekurencję (na początek).

1
function f(n) {
    if (n == 0) { return 0; }
    if (n == 1) { return 1; }

    return f(n - 1) + f(n - 2);
}

Zadziała tak:

f(6) =
f(5) + f(4) =
(f(4) + f(3)) + (f(3) + f(2)) =
((f(3) + f(2)) + (f(2) + f(1)) + (f(2) + f(1)) + f(1) + f(0))
I tak dalej, aż wszystkie wywołania będą miały parametr równy 0 albo 1.

0

Weź jak człowiek cywilizowany długopis/ołówek oraz kartkę papieru i rozrysuj se drzewko wywołań.

1 użytkowników online, w tym zalogowanych: 0, gości: 1