На этом шаге мы поясним понятие взаимной рекурсии.
Метод, явно вызывающий сам себя, рекурсивен по определению. Однако рекурсивный метод не обязательно вызывает себя явно. Он может быть вызван другим методом, который, в свою очередь, вызывает его. Таким образом, вызов метода может повлечь множество последующих обращений к нему. Такой тип рекурсии называют взаимной, или косвенной, рекурсией.
Вообще говоря, несколько методов взаимно-рекурсивны, если они вызывают друг друга циклически. Для примера рассмотрим множество методов {f1, f2, ..., fn}. Если f1 вызывает f2, f2 вызывает f3 и т. д. и, наконец, fn вызывает f1, то говорят, что эти методы взаимно-рекурсивны. При этом они не обязаны вызывать друг друга строго циклически. Они могут вызвать несколько методов, включая себя, как показано на рисунке 1, где стрелки означают вызов метода (например, f8 вызывает f1 и f4).
Рис.1. Вызовы взаимно-рекурсивных методов
В этом примере только f3 вызывает себя явно, а все остальные методы взаимно-рекурсивны.
На первом шаге применения взаимной рекурсии задача разбивается на несколько разных задач (а не просто подзадач). После чего каждая из этих задач решается рекурсивно, опираясь на решения своих подзадач. Для взаимной рекурсии характерно то, что при решении некоторой задачи P используются рекурсивные решения подзадач, которые не обязательно являются меньшими экземплярами P. Конечно, разбиение исходной задачи на несколько разных задач требует больше труда. Но как только эти задачи определены, процесс рекурсивного проектирования уподобляется работе с единственным методом. Иными словами, мы, как обычно, применяем декомпозицию и индукцию. Более того, бОльшая сложность задач и характер их декомпозиции только подчеркнут важность этих принципиальных понятий.
На следующем шаге мы рассмотрим чётность числа.
