опашката рекурсия

Опашката рекурсия - специален случай на рекурсия. където всяка рекурсивно повикване е последната сделка преди да се върнат от функцията. [1] Този тип рекурсия е забележителна с това, че лесно може да бъде заменен с повторение от формално и гарантирана правилната настройка функция код. Оптимизация на опашка рекурсия, като го превръща в плоска итерация се осъществява в много оптимизиране компилатори. Някои функционални програмни езици, спецификация осигурява задължително оптимизация опашката рекурсия.

Опашката рекурсия често се използва в програми за функционални програмни езици. Много изчисления на следните езици естествено, изразени под формата на рекурсивни функции, както и способността да се замества автоматично преводач опашка рекурсия за повторение на означава, че изчислителната ефективност е равна на еквивалентен код написан на един повтарящ се начин.

Създателите на Схема функционален език. един от най-Lisp диалекти. Ние оценявам значението на опашка рекурсия, така че спецификацията на език, предписан всеки съставител на този език е задължително за изпълнение оптимизация опашката рекурсия и опишете точния набор от условия, за да бъдат изпълнени от рекурсивни функции за рекурсия тя е оптимизирана. [2]

Пример за рекурсивни функции за изчисляване на факториел. използване на опашка рекурсия на езика по Схема за програмиране и C:

В този пример, въпреки факта, че функцията за рекурсивно повикване в текста е на дъното, автоматична оптимизация рекурсия не работи, тъй като в действителност последното извършва операцията е операцията умножение се п. и по този начин състоянието на опашката рекурсия не се извършва. По-горе опашната факторен рекурсивни изпълнения са модификации очевиден начин, който е точно насочен към размножаването на прехвърляне. Отнесен към този метод, между другото, той е един от стандартните начини да донесат рекурсия на опашката-рекурсивни ума. Тя се крие във факта, че множеството на местните данни, които трябва да се съхраняват при рекурсивно повикване се прехвърля на параметрите на функцията обаждане. В случай на дадения пример факторните такъв параметър е променлива съгл. което води до възникване на натрупване.

Като цяло, такива модификации могат да бъдат достатъчно нетривиални. По-специално, възможно е опашната-рекурсивния е само един от "най-проблемни" клон на изпълнението на функция, а други са рекурсивни.