Rekursja Ogonowa

0

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.

1

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
0

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.

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