@hleb1
Очень тупой, но стремится поумнеть. Сжалься

В чем отличие рекурсивного процесса от процедуры?

Читаю SICP. Там приводится объяснение объяснение между рекурсивным процессом и процедурой. Но я понял не до конца. Типо рекурсивный процеСС - это и есть рекурсия во всех ее прелестях, а вот рекурсивная процеДУРА - может создавать либо рекурсивный процеСС, либо итерационный (хвостовая рекурсия)?
  • Вопрос задан
  • 280 просмотров
Решения вопроса 1
zagayevskiy
@zagayevskiy
Android developer at Yandex
Из твоего описания, вроде, всё понятно.
Вот есть рекурсивная процедура (мне лично ближе название функция). Она рекурсивная по определению – потому что прямо или опосредованно вызывает сама себя.

А вот процесс выполнения этой функции может пойти двумя разными путями, в зависимости от того, как написана функция, и поддерживает ли реализация языка оптимизацию хвостовой рекурсии(TСO, Tail call optimization).

Если ТСО нет, то процесс выполнения такой функции будет рекурсивным, то есть будут создаваться фреймы на стеке, и всё это может привести к stack overflow(нехватке стековой памяти при вызове функции).

В лиспе и его диалектах ТСО есть. Значит, если функция написана правильно(а это значит, что рекурсивный вызов является последним действием перед выходом из функции), то её можно оптимизировать в итерацию, и таким образом сэкономить на выделениях стека.
Следовательно, процесс выполнения такой функции будет итеративным. Хвостовая рекурсия может выполняться бесконечно долго без stack overflow.
Если же функция рекурсивная, но рекурсия не хвостовая, то и процесс её выполнения будет рекурсивным со всеми вытекающими.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы