LINUX.ORG.RU
Форум — Development  

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


0

0

Здравствуйте!

Недавно узнал, что существует такое свойство реализации языка, как хвостовая рекурсия, которое заключается в том, что даже если процесс описывается рекурсивной процедурой, он будет выполняться как итеративный процесс, используя фиксированный объём памяти. Но я не смог найти соответствующий алгоритм преобразования для императивных программ (линейно рекурсивная -> линейно итеративная), может быть кто-нибудь может поделиться ссылками или ещё чем-нибудь.

anonymous

> алгоритм преобразования для императивных программ (линейно рекурсивная -> линейно итеративная)

аргумент функции делаешь индексом цикла.

Типа если была ф-ция:

A f(B arg)
{
    if(...) {
        some_code1
        return 5
    }
    else {
        some_code2
        return f(...)
    }
}

превращается в:

A f(B arg)
{
    B i = arg;
    while (1) {
        if(...) {
            some_code1
            return 5
        }
        else {
            some_code2
            i = f(...)
            continue;
        }
    }
}

dilmah ★★★★★
()

а что такое линейно рекурсивная и линейно итеративная?

dilmah ★★★★★
() 

Вместо
  call self
  ret
ставишь
  jmp self
и усё.

Miguel ★★★★★
()
Ответ на: комментарий от dilmah

>аргумент функции делаешь индексом цикла.

это очень частный случай. хвостовая рекурсия вообще является частным случаем last call optimisation, что очень точно характеризует процесс.

Pi ★★★★★
()

int f(x) { ... label:

... if(...) goto label; else return ...; }

fk0 ★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development