En matemáticas y ciencias de la computación , la recursión mutua es una forma de recursión donde dos objetos matemáticos o computacionales, como funciones o tipos de datos, se definen en términos uno del otro. [1] La recursión mutua es muy común en la programación funcional y en algunos dominios de problemas, como los analizadores sintácticos de descenso recursivo , donde los tipos de datos son naturalmente recursivos entre sí.
El ejemplo básico más importante de un tipo de datos que se puede definir mediante recursión mutua es un árbol , que se puede definir recursivamente de forma mutua en términos de un bosque (una lista de árboles). Simbólicamente:
f: [t[1], ..., t[k]]t: vf
Un bosque f consiste en una lista de árboles, mientras que un árbol t consiste en un par de valores v y un bosque f (sus hijos). Esta definición es elegante y fácil de usar de manera abstracta (por ejemplo, al demostrar teoremas sobre propiedades de árboles), ya que expresa un árbol en términos simples: una lista de un tipo y un par de dos tipos. Además, coincide con muchos algoritmos sobre árboles, que consisten en hacer una cosa con el valor y otra con los hijos.
Esta definición recursiva mutua se puede convertir en una definición recursiva simple incorporando en línea la definición de un bosque:
t: v [t[1], ..., t[k]]
Un árbol t consta de un par de valores v y una lista de árboles (sus hijos). Esta definición es más compacta, pero algo más confusa: un árbol consta de un par de un tipo y una lista de otro, que requieren desenredarse para demostrar resultados.
En ML estándar , los tipos de datos de árbol y bosque se pueden definir recursivamente de la siguiente manera, lo que permite árboles vacíos: [2]
tipo de datos 'un árbol = Vacío | Nodo de 'a * 'un bosque y 'a bosque = Nil | Contras de 'a árbol * 'un bosqueAsí como los algoritmos sobre tipos de datos recursivos pueden ser dados naturalmente por funciones recursivas, los algoritmos sobre estructuras de datos mutuamente recursivas pueden ser dados naturalmente por funciones mutuamente recursivas. Los ejemplos comunes incluyen algoritmos sobre árboles y analizadores de descenso recursivos . Al igual que con la recursión directa, la optimización de llamadas de cola es necesaria si la profundidad de recursión es grande o ilimitada, como usar la recursión mutua para multitarea. Tenga en cuenta que la optimización de llamadas de cola en general (cuando la función llamada no es la misma que la función original, como en las llamadas recursivas de cola) puede ser más difícil de implementar que el caso especial de optimización de llamadas recursivas de cola y, por lo tanto, la implementación eficiente de la recursión de cola mutua puede estar ausente de los lenguajes que solo optimizan las llamadas recursivas de cola. En lenguajes como Pascal que requieren declaración antes del uso, las funciones mutuamente recursivas requieren declaración hacia adelante , ya que no se puede evitar una referencia hacia adelante al definirlas.
Al igual que con las funciones directamente recursivas, una función contenedora puede ser útil, con las funciones recursivas mutuas definidas como funciones anidadas dentro de su alcance si esto es posible. Esto es particularmente útil para compartir el estado entre un conjunto de funciones sin tener que pasar parámetros entre ellas.
Un ejemplo estándar de recursión mutua, que ciertamente es artificial, determina si un número no negativo es par o impar definiendo dos funciones separadas que se llaman entre sí, decrementándose en 1 cada vez. [3] En C:
bool is_even ( unsigned int n ) { si ( n == 0 ) devuelve verdadero ; de lo contrario devuelve is_odd ( n - 1 ); } bool is_odd ( unsigned int n ) { si ( n == 0 ) devuelve falso ; de lo contrario devuelve is_even ( n - 1 ); } Estas funciones se basan en la observación de que la pregunta es 4 even? es equivalente a es 3 odd? , que a su vez es equivalente a es 2 even? , y así sucesivamente hasta 0. Este ejemplo es recursión simple mutua y podría reemplazarse fácilmente por iteración. En este ejemplo, las llamadas recursivas mutuas son llamadas de cola y sería necesaria la optimización de llamadas de cola para ejecutar en un espacio de pila constante. En C, esto ocuparía O ( n ) espacio de pila, a menos que se reescriba para usar saltos en lugar de llamadas. [4] Esto podría reducirse a una sola función recursiva is_even. En ese caso, is_odd, que podría estar en línea, llamaría a is_even, pero is_evensolo se llamaría a sí mismo.
Como una clase más general de ejemplos, un algoritmo en un árbol se puede descomponer en su comportamiento en un valor y su comportamiento en los hijos, y se puede dividir en dos funciones recursivas entre sí, una que especifica el comportamiento en un árbol, llamando a la función de bosque para el bosque de hijos, y otra que especifica el comportamiento en un bosque, llamando a la función de árbol para el árbol en el bosque. En Python:
def f_tree ( árbol ) -> None : f_value ( árbol . valor ) f_forest ( árbol . hijos )def f_forest ( bosque ) -> None : para árbol en bosque : f_tree ( árbol )En este caso, la función de árbol llama a la función de bosque mediante recursión simple, pero la función de bosque llama a la función de árbol mediante recursión múltiple .
Utilizando el tipo de datos ML estándar mencionado anteriormente, el tamaño de un árbol (número de nodos) se puede calcular mediante las siguientes funciones recursivas entre sí: [5]
diversión tamaño_árbol Vacío = 0 | tamaño_árbol ( Nodo (_, f )) = 1 + tamaño_bosque f y tamaño_bosque Nil = 0 | tamaño_bosque ( Cons ( t , f' )) = tamaño_árbol t + tamaño_bosque f'Un ejemplo más detallado en Scheme , contando las hojas de un árbol: [6]
( define ( count-leafes tree ) ( if ( leaf? tree ) 1 ( count-leafes-in-forest ( children tree )))) ( define ( count-leafves-in-forest forest ) ( if ( null? forest ) 0 ( + ( count-leafves ( car forest )) ( count-leafves-in-forest ( cdr forest ))))) Estos ejemplos se reducen fácilmente a una única función recursiva al incorporar la función de bosque en la función de árbol, lo que se hace comúnmente en la práctica: las funciones directamente recursivas que operan en árboles procesan secuencialmente el valor del nodo y recurren a los hijos dentro de una función, en lugar de dividirlos en dos funciones separadas.
Un ejemplo más complicado lo dan los analizadores sintácticos descendentes recursivos , que se pueden implementar de forma natural al tener una función para cada regla de producción de una gramática, que luego recurren mutuamente; esto en general será recursión múltiple, ya que las reglas de producción generalmente combinan múltiples partes. Esto también se puede hacer sin recursión mutua, por ejemplo, al tener funciones separadas para cada regla de producción, pero que sean llamadas por una única función de controlador, o al poner toda la gramática en una única función.
La recursión mutua también puede implementar una máquina de estados finitos , con una función para cada estado y una única recursión en el cambio de estado; esto requiere la optimización de llamadas de cola si el número de cambios de estado es grande o ilimitado. Esto se puede utilizar como una forma simple de multitarea cooperativa . Un enfoque similar a la multitarea es utilizar corrutinas que se llaman entre sí, donde en lugar de terminar llamando a otra rutina, una corrutina cede el paso a otra pero no termina, y luego reanuda la ejecución cuando se le cede el paso. Esto permite que las corrutinas individuales mantengan el estado, sin necesidad de pasarlo por parámetros o almacenarlo en variables compartidas.
También hay algunos algoritmos que naturalmente tienen dos fases, como minimax (min y max), que pueden implementarse teniendo cada fase en una función separada con recursión mutua, aunque también pueden combinarse en una sola función con recursión directa.
En matemáticas, las secuencias femenina y masculina de Hofstadter son un ejemplo de un par de secuencias de números enteros definidas de manera mutuamente recursiva.
Los fractales se pueden calcular (hasta una resolución determinada) mediante funciones recursivas. A veces, esto se puede hacer de forma más elegante mediante funciones recursivas mutuas; la curva de Sierpiński es un buen ejemplo.
La recursión mutua es muy común en la programación funcional y se utiliza a menudo para programas escritos en LISP , Scheme , ML y lenguajes de programación similares . Por ejemplo, Abelson y Sussman describen cómo se puede utilizar un evaluador metacircular para implementar LISP con un ciclo de evaluación-aplicación. [7] En lenguajes como Prolog , la recursión mutua es casi inevitable.
Algunos estilos de programación desaconsejan la recursión mutua, alegando que puede resultar confuso distinguir las condiciones que devolverán una respuesta de las condiciones que permitirían que el código se ejecute indefinidamente sin producir una respuesta. Peter Norvig señala un patrón de diseño que desaconseja su uso por completo, afirmando: [8]
Si tiene dos funciones recursivas entre sí que alteran el estado de un objeto, intente trasladar casi toda la funcionalidad a una sola de las funciones. De lo contrario, probablemente terminará duplicando el código.
La recursión mutua también se conoce como recursión indirecta , en contraste con la recursión directa , donde una sola función se llama a sí misma directamente. Esto es simplemente una diferencia de énfasis, no una noción diferente: la "recursión indirecta" enfatiza una función individual, mientras que la "recursión mutua" enfatiza el conjunto de funciones y no destaca una función individual. Por ejemplo, si f se llama a sí misma, eso es recursión directa. Si en cambio f llama a g y luego g llama a f, que a su vez llama a g nuevamente, desde el punto de vista de f solo, f es recursiva indirectamente, mientras que desde el punto de vista de g solo, g es recursiva indirectamente, mientras que desde el punto de vista de ambos, f y g son mutuamente recursivas entre sí. De manera similar, un conjunto de tres o más funciones que se llaman entre sí puede llamarse un conjunto de funciones mutuamente recursivas.
Matemáticamente, un conjunto de funciones recursivas mutuas son recursivas primitivas , lo que se puede demostrar mediante la recursión de curso de valores , construyendo una única función F que enumera los valores de la función recursiva individual en orden: y reescribiendo la recursión mutua como una recursión primitiva.
Cualquier recursión mutua entre dos procedimientos se puede convertir en recursión directa insertando el código de un procedimiento en el otro. [9] Si solo hay un sitio donde un procedimiento llama al otro, esto es sencillo, aunque si hay varios puede implicar duplicación de código. En términos de la pila de llamadas, dos procedimientos mutuamente recursivos producen una pila ABABAB..., y la inserción de B en A produce la recursión directa (AB)(AB)(AB)...
Alternativamente, cualquier número de procedimientos se puede fusionar en un solo procedimiento que toma como argumento un registro de variante (o tipo de datos algebraicos ) que representa la selección de un procedimiento y sus argumentos; el procedimiento fusionado luego envía su argumento para ejecutar el código correspondiente y usa recursión directa para llamar a self según sea apropiado. Esto puede verse como una aplicación limitada de la desfuncionalización . [10] Esta traducción puede ser útil cuando cualquiera de los procedimientos recursivos entre sí puede ser llamado por código externo, por lo que no hay un caso obvio para incrustar un procedimiento en el otro. Dicho código debe modificarse para que las llamadas a procedimientos se realicen agrupando argumentos en un registro de variante como se describe; alternativamente, se pueden usar procedimientos envolventes para esta tarea.
