Косвенная рекурсия

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

напрямую, а через другую процедуру (или функцию). Это описывается следующей схемой:

Не допустим бесконечную рекурсию!

При использовании рекурсивных процедур и функций велика опасность, что вложенные

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

Для функции вычисления факториала таким условием является n <= 0. Докажем, что рекурсия в примере, рассмотренном выше, закончится.

1. Рекурсивные вызовы заканчиваются, когда nстановится равно нулю.

2. При каждом новом рекурсивном вызове значение nуменьшается на 1 (это следует из того,что вызывается Factorial(n-1,...)).

3. Поэтому, если в началеn > 0, то, постепенно уменьшаясь, nдостигает значения 0и рекурсия заканчивается.

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