Хвостова рекурсія

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Хвостова рекурсія — це випадок рекурсії, коли рекурсивний виклик функції відбувається наприкінці її роботи. Це використовується в функціональних мовах програмування для оптимізації, через можливість заміни хвостової рекурсії на ітерацію.

Опис[ред.ред. код]

Коли відбувається виклик функції комп'ютер має запам'ятати адресу повернення, щоб після завершення викликаної функції повернутися і продовжити виконання програми. Зазвичай адреса виконання зберігається у стеку. Іноді, остання дія функції після завершення всіх інших операцій, це просто виклик функції, можливо самої себе, і повернення результату. В цьому випадку немає необхідності запам'ятовувати адресу повернення, нововикликана функція буде повертати результат безпосередньо за адресою повернення записаною для початкової функції.

Приклади[ред.ред. код]

Приклад на Scheme:

(define (factorial n)
  (define (fac-times n acc)
    (if (= n 0)
        acc
        (fac-times (- n 1) (* acc n))))
  (if (< n 0)
      (display "Невірний параметр!")
      (fac-times n 1)))

Приклад на Scala:

def factorial(x: BigInt) = {
 
  def f2(x: BigInt, sum: BigInt): BigInt =
    if (x == 1) sum else f2(x - 1, x * sum)
 
  f2(x, 1)
}

Приклад на Erlang:

-module(test).
-export([fac/1]).
fac(N) -> fac(N,1).
 
fac(0,A) -> A;
fac(N,A) -> fac(N-1,N*A).

Див. також[ред.ред. код]