Прежде чем мы углубимся в суть, давайте повторим некоторые основы.

Рекурсия. Это процесс, в котором функция многократно вызывает сама себя до тех пор, пока не будет достигнуто базовое условие или не будет достигнут желаемый результат.

Базовое условие. Это условие, при котором функция перестает делать рекурсивные вызовы и начинает возвращать результат. И если это условие не определено, программа может попасть в бесконечный цикл, который вызовет Ошибку переполнения стека, так как память стека будет потрачена впустую.

Ошибка переполнения стека. Чтобы лучше понять, что это такое, обратитесь к моей статье Как функции работают внутри, чтобы узнать о программном стеке, фрейме стека. и все остальное.

Таким образом,эта ошибка возникает, когда память стека исчерпывается из-за большого количества входящих кадров стека, которые больше не могут быть размещены в стеке.

Итак, теперь приступим к теме.

Что такое хвостовая рекурсия?

Рекурсивная функция является хвостовой рекурсией, если рекурсивный вызов выполняется функцией последним.

Я знаю, что это мало что объяснило по теме. Итак, давайте сначала посмотрим, что такое нехвостовая рекурсия, то есть традиционная рекурсия, которую мы все используем в основном.

  • В традиционной/нехвостовой рекурсии типичная модель заключается в том, что сначала вы выполняете свои рекурсивные вызовы, затем берете возвращаемое значение рекурсивных вызовов и вычисляете результат. Таким образом, вы не получите результат своего вычисления, пока не вернетесь из каждого рекурсивного вызова. Например:

Для приведенного выше псевдокода поток управления будет таким:

Можно сказать, что для вычисления результата каждый рекурсивный вызов должен сначала завершить свою операцию.

  • Теперь, в хвостовой рекурсии, вы сначала выполняете свои вычисления, а затем выполняете рекурсивный вызов, передавая результат вашего текущего шага на следующий шаг. Таким образом, возвращаемое значение любого данного рекурсивного шага совпадает с возвращаемым значением следующего рекурсивного вызова. Давайте визуализируем это через псевдокод и его поток управления.

Следствием хвостовой рекурсии является то, что когда программа готова выполнить следующий рекурсивный шаг, ей больше не нужен текущий кадр стека в стеке программы. Это позволяет провести некоторую оптимизацию, как видно из рис. (B) и (D), что процесс вычисления хвостовой рекурсии занимает гораздо меньше времени, чем время, необходимое для нехвостовой рекурсии. С функцией хвостовой рекурсии Ошибка переполнения стека может не возникнуть.

Это все, что вам нужно знать о хвостовой рекурсии.

Если вы нашли статью интересной, сообщите мне об этом в разделе комментариев или, если у вас есть какие-либо сомнения по этому поводу, оставьте их в том же месте, я постараюсь решить эту проблему как можно скорее.

Спасибо за прочтение ❤️