На этом шаге мы дадим понятие такого типа рекурсии.
Говорят, что несколько методов относится к типу взаимно-рекурсивных, если они могут вызывать друг друга циклически. Например, функция f() может вызывать другую функцию g(), которая, в свою очередь, может вызвать третью функцию h(), которая может завершаться вызовом первой функции f(). Такую рекурсию называют ещё "косвенной", поскольку метод вызывает себя не непосредственно внутри своего тела, а через циклическую цепочку вызовов. Например, рассмотрим две следующие функции Фибоначчи:
0, если n = 1
A(n) = (1.17)
A(n - 1) + B(n - 1), если n > 1
1, если n = 1
B(n) = (1.18)
A(n - 1), если n > 1
Ясно, что A() рекурсивна, так как вызывает саму себя, но рекурсия в B() - косвенная, так как вызывает A(), которая, в свою очередь, вызывает B(). Таким образом, рекурсия возникает из-за того, что вызов B() может породить другие вызовы B() (в более простых экземплярах задачи). Эти функции также могут применяться для генерации чисел Фибоначчи. В частности, F(n) = B(n) + A(n). Взаимную рекурсию также планируется рассмотреть более подробно.
На следующем шаге мы рассмотрим вложенную рекурсию.
