Есть ли какой-либо пример Взаимной рекурсии?
Есть ли какие-либо примеры для рекурсивной функции, которая вызывает другую функцию, которая называет первый также?
Пример:
function1()
{
//do something
f2();
//do something
}
function2()
{
//do something
f1();
//do something
}
5 ответов
Взаимная рекурсия обычна в коде, который анализирует математические выражения (и другие грамматики). Парсер рекурсивного спуска, основанный на грамматике ниже, естественно, будет содержать взаимную рекурсию: выражение-термины-термин-фактор-первичное-выражение .
expression
+ terms
- terms
terms
terms
term + terms
term - terms
term
factor
factor * term
factor / term
factor
primary
primary ^ factor
primary
( expression )
number
name
name ( expression )
Это немного надумано и не очень эффективно, но вы можете сделать это с функцией для вычисления чисел Фиббоначи, как в:
fib2(n) { return fib(n-2); }
fib1(n) { return fib(n-1); }
fib(n)
{
if (n>1)
return fib1(n) + fib2(n);
else
return 1;
}
В этом случае его эффективность может быть значительно повышена, если язык поддерживает мемоизацию
Правильный термин для этого - взаимная рекурсия.
http://en.wikipedia.org/wiki/Mutual_recursion
На этой странице есть пример, который я воспроизведу здесь на Java:
boolean even( int number )
{
if( number == 0 )
return true;
else
return odd(abs(number)-1)
}
boolean odd( int number )
{
if( number == 0 )
return false;
else
return even(abs(number)-1);
}
Где abs (n) означает возврат абсолютного значения числа .
Ясно, что это неэффективно, просто чтобы продемонстрировать точку зрения.
Примером может служить алгоритм minmax, обычно используемый в игровых программах, таких как шахматы. Начиная с вершины игрового дерева, цель состоит в том, чтобы найти максимальное значение всех узлов на уровне ниже, значения которого определены как минимум значений узлы ниже этого, значения которых определены как максимум значений ниже этого, чьи значения ...
В языке с правильными хвостовыми вызовами Mutual Tail Recursion - очень естественный способ реализации автоматов.