На этом шаге мы дадим определение этому типу рекурсии.
Рекурсия множественного типа возникает, когда в каком-то рекурсивном условии метод вызывает себя несколько раз. Если метод вызывает себя дважды, то такой тип рекурсии называют "двойной рекурсией" ("binary recursion"). Из приведённых ранее примеров к данному типу рекурсии относятся (1.2), (1.6), (1.7) и (1.11). Следующая функция использует множественную рекурсию для альтернативного определения чисел Фибоначчи, где F(n) = f(n):
1, если n = 1 или n = 2,
f(n) = f(n / 2 + 1)2 - f(n / 2 - 1)2, если n > 2 и n - чётное, (1.16)
f((n + 1) / 2)2 + f((n - 1) / 2)2, если n > 2 и n - нечётное.
Такой тип рекурсии обычно возникает в алгоритмах, разработанных согласно стратегии "разделяй и властвуй".
На следующем шаге мы рассмотрим взаимную рекурсию.
