На этом шаге мы приведем пример такого типа рекурсии.
Вложенный тип рекурсии возникает, когда аргумент рекурсивной функции содержит другой рекурсивный вызов. Рассмотрим следующую функцию Фибоначчи:
1 + s, если n = 1 или n = 2
f(n, s) = (1.19)
f(n - 1, s + f(n - 2, 0)), если n > 2
Второй параметр рекурсивного вызова - выражение, включающее в себя еще один рекурсивный вызов функции. В этом случае числа Фибоначчи F(n) могут быть получены из f(n, 0). Такой тип рекурсии редок, но появляется в некоторых задачах и контекстах, связанных с хвостовой рекурсией. Краткий обзор вложенной рекурсии мы приведем чуть позже.
Со следующего шага мы начнем разбираться с методикой рекурсивного мышления.
