Какой термин для «двойной рекурсии»?

Question

Вот явно рекурсивная функция:

function()
{
    function();
}

Мы бы просто назвали это "рекурсивным", но как насчет этой (едва ли) более сложной версии?

functionLeft()
{
    functionRight();
}

functionRight()
{
    functionLeft();
}

Есть ли термин для этого сценария, например, "двойная рекурсия"? Или нет конкретного термина, отличающего этот случай от описанного выше случая с одной функцией?

Answer 1

Это называется взаимная рекурсия .

Answer 2

Как сказал Джон Пурди, приведенный вами пример называется "взаимной рекурсией". Термин «двойная рекурсия» также существует, но имеет другое значение: для случая, когда функция использует два рекурсивных вызова. Классическим примером является функция Фибоначчи "

int Fib(int n)
{
  if (n < 2) return 1;
  return Fib(n-1) + Fib(n-2);
}

Функция Fib (n) рекурсивно вызывает себя дважды.

Answer 3

Одной из взаимосвязей двойной рекурсии может быть разделить и победить (например) быстрая сортировка

quicksort = quicksort smaller ++ pivot ++ quicksort larger