Хвостова рекурсія — Вікіпедія

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (липень 2013)

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

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

Приклад на 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). 

• Стек викликів
• Переповнення буфера
• Погодження виклику

Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її.