|
Когда функция вызвает другую функцию (себя, как частный случай) она кладет на стек (который имет фиксированный и довольно небольшой размер) переменные, которые надо передать в функцию, и адрес возврата.
В рекурсивных программах глубина рекурсии может быть большой и стек может "внезапно переполнится". Если компилятор поддерживает оптимизацию хвостовой рекурсии и мы правильно написали программу (оба момента важны - не любую рекурсию можно оптимизировать), то мы можем избежать использования стека.
Для того, чтобы эта магия произошла рекурсивный вызов должен быть последней операцией в вызывающей функции. А результатом функции должен быть результат вот этого рекурсивного вызова. В этом случае адрес возврата и так находится в стеке, а значения параметров просто подменяются на новые.
Получается, что стек не растет по мере рекурсивного вызова функций (а это критично для функциональных языков программирования, где цикл сделать не всегда возможно) независимо от глубины рекурсии.
|