Czy może ktoś napisać mi (Najlepiej na jakimś przykładzie - Scala, Ocaml) na czym polega Rekursja Ogonowa?
Wiem że tam trzeba dodać zmienną -> Akumulator, ale nie mogę znaleźć nigdzie jakiegoś dobrego wytłumaczenia do tego.
Czy może ktoś napisać mi (Najlepiej na jakimś przykładzie - Scala, Ocaml) na czym polega Rekursja Ogonowa?
Wiem że tam trzeba dodać zmienną -> Akumulator, ale nie mogę znaleźć nigdzie jakiegoś dobrego wytłumaczenia do tego.
Polega to na tym, że przy "normalnej" rekurencji tworzy się drzewo wywołań. Np.:
(define (factorial n)
(if (< n 2)
1
(* n (factorial (- n 1)))))
To będzie wywołane tak:
"CALLED" factorial 6
"CALLED" factorial 5
"CALLED" factorial 4
"CALLED" factorial 3
"CALLED" factorial 2
"CALLED" factorial 1
"CALLED" factorial 0
"RETURNED" factorial 1
"RETURNED" factorial 1
"RETURNED" factorial 2
"RETURNED" factorial 6
"RETURNED" factorial 24
"RETURNED" factorial 120
"RETURNED" factorial 720
Co jak widać powoduje zagłębione wywołanie funkcji. Jeśli napiszemy to tak:
(define (factorial n)
(let loop ((n n)
(acc 1))
(if (zero? n)
acc
(loop (- n 1) (* acc n)))))
To wtedy zamiast tworzyć drzewo rekursji będzie to bardziej goto
ze zmianą parametrów. Można by to zapisać w takiej postaci:
n
acc = 1
loop:
if n == 0
return acc
acc = acc * n
n = n - 1
goto loop
Wydaje mi się że to juz zrozumiałem, problem tkwił w tym że nie wiedziałem jak wykorzystać akumulator. Pomogło przerobienie sobie krok po kroku przykładów na kartce.