На этом шаге мы приведем общие сведения о такой рекурсии.

Вложенная рекурсия - довольно редкий тип рекурсии, когда рекурсивная функция вызывается в аргументе рекурсивного метода. Подобно хвостовым рекурсивным функциям во многих функциях с вложенной рекурсией (в частности, во всех, представленных в этих шагах), рекурсивный вызов - это последнее действие, выполняемое алгоритмом. Тем не менее методы с вложенной рекурсией обязательно должны вызывать себя несколько раз хотя бы в одном из рекурсивных условий. Следовательно, их нельзя отнести к хвостовой рекурсии. Начиная с этого шага, описываются две известные функции с вложенной рекурсией и одна задача, которая решается таким же образом.

На следующем шаге мы рассмотрим функцию Аккермана.