En matemáticas e informática , la recursividad mutua es una forma de recursividad en la que dos objetos matemáticos o computacionales, como funciones o tipos de datos, se definen entre sí. [1] La recursión mutua es muy común en la programación funcional y en algunos dominios de problemas, como los analizadores 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 puede definirse mediante recursividad mutua es un árbol , que puede definirse mutuamente recursivamente en términos de un bosque (una lista de árboles). Simbólicamente:
f: [t[1], ..., t[k]]t:vf
Un bosque f consta de una lista de árboles, mientras que un árbol t consta de un par de un valor v y un bosque f (sus hijos). Esta definición es elegante y fácil de trabajar de forma abstracta (como cuando se demuestran 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 en árboles, que consisten en hacer una cosa con el valor y otra con los hijos.
Esta definición mutuamente recursiva se puede convertir en una definición recursiva individualmente insertando la definición de un bosque:
t: v [t[1], ..., t[k]]
Un árbol t consta de un par de un valor 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 Standard ML , los tipos de datos de árbol y bosque se pueden definir mutuamente de forma recursiva de la siguiente manera, permitiendo árboles vacíos: [2]
tipo de datos 'un árbol = Vacío | Nodo de 'a * 'a bosque y 'a bosque = Nil | Contras de 'un arbol * 'un bosqueAsí como los algoritmos sobre tipos de datos recursivos pueden estar dados naturalmente por funciones recursivas, los algoritmos sobre estructuras de datos mutuamente recursivas pueden estar dados naturalmente por funciones mutuamente recursivas. Los ejemplos comunes incluyen algoritmos sobre árboles y analizadores de descenso recursivos . Al igual que con la recursividad directa, la optimización de las llamadas de cola es necesaria si la profundidad de la recursividad es grande o ilimitada, como en el caso del uso de la recursividad mutua para realizar múltiples tareas. 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, una implementación eficiente de La recursividad de cola mutua puede estar ausente en los lenguajes que solo optimizan las llamadas recursivas de cola. En lenguajes como Pascal que requieren una declaración antes de su uso, las funciones mutuamente recursivas requieren una declaración directa , ya que no se puede evitar una referencia directa al definirlas.
Al igual que con las funciones directamente recursivas, una función contenedora puede ser útil, con las funciones mutuamente recursivas definidas como funciones anidadas dentro de su alcance, si esto es compatible. 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 recursividad mutua, que es ciertamente artificial, determina si un número no negativo es par o impar definiendo dos funciones separadas que se llaman entre sí, disminuyendo en 1 cada vez. [3] En C:
bool is_even ( unsigned int n ) { if ( 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 ¿par? ¿equivale a 3 impar? , que a su vez equivale a ¿2 es par? y así sucesivamente hasta 0. Este ejemplo es una recursión única mutua y podría reemplazarse fácilmente por una iteración. En este ejemplo, las llamadas mutuamente recursivas son llamadas de cola , y sería necesaria la optimización de las llamadas de cola para ejecutarlas 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 única función recursiva is_even. En ese caso, is_odd, que podría estar incluido, 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 sobre un valor y su comportamiento sobre los niños, y se puede dividir en dos funciones mutuamente recursivas, una que especifica el comportamiento en un árbol y llama al bosque. función para el bosque de niños, 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 ) -> Ninguno : f_value ( árbol . valor ) f_forest ( árbol . hijos )def f_forest ( bosque ) -> Ninguno : para árbol en el bosque : f_tree ( árbol )En este caso, la función de árbol llama a la función de bosque mediante recursividad única, pero la función de bosque llama a la función de árbol mediante recursividad múltiple .
Utilizando el tipo de datos Standard ML anterior, el tamaño de un árbol (número de nodos) se puede calcular mediante las siguientes funciones mutuamente recursivas: [5]
divertido size_tree Vacío = 0 | size_tree ( Nodo (_, f )) = 1 + size_forest f y size_forest Nil = 0 | size_forest ( Contras ( t , f' )) = size_tree t + size_forest f'Un ejemplo más detallado en Scheme , contando las hojas de un árbol: [6]
( definir ( árbol de contar hojas ) ( si ( árbol de hoja ) 1 ( contar hojas en el bosque ( árbol de niños )))) ( definir ( contar-hojas-en-bosque bosque ) ( if ( null? bosque ) 0 ( + ( contar-hojas ( coche bosque )) ( contar-hojas-en-bosque ( cdr bosque ))))) Estos ejemplos se reducen fácilmente a una única función recursiva al incluir 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 en los hijos dentro de una función, en lugar de que dividirlas en dos funciones separadas.
Un ejemplo más complicado lo dan los analizadores de descenso recursivos , que pueden implementarse naturalmente al tener una función para cada regla de producción de una gramática, que luego se repiten mutuamente; En general, esto será una recursión múltiple, ya que las reglas de producción generalmente combinan varias partes. Esto también se puede hacer sin recursividad mutua, por ejemplo, manteniendo funciones separadas para cada regla de producción, pero llamándolas mediante una única función de controlador, o poniendo toda la gramática en una sola función.
La recursividad mutua también puede implementar una máquina de estados finitos , con una función para cada estado y una recursividad única en el estado cambiante; esto requiere 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 sencilla 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 devuelve 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 se pueden implementar teniendo cada fase en una función separada con recursividad mutua, aunque también se pueden combinar en una sola función con recursividad directa.
En matemáticas, las secuencias femenina y masculina de Hofstadter son un ejemplo de un par de secuencias enteras 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 manera más elegante mediante funciones mutuamente recursivas; la curva de Sierpiński es un buen ejemplo.
La recursividad 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 recursividad mutua es casi inevitable.
Algunos estilos de programación desaconsejan la recursividad 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 para siempre sin producir una respuesta. Peter Norvig señala un patrón de diseño que desaconseja por completo su uso, afirmando: [8]
Si tiene dos funciones mutuamente recursivas y ambas alteran el estado de un objeto, intente mover casi toda la funcionalidad a solo una de las funciones. De lo contrario, probablemente terminarás duplicando el código.
La recursividad mutua también se conoce como recursividad indirecta , en contraste con la recursividad directa , donde una única 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 señala una función individual. Por ejemplo, si f se llama a sí mismo, eso es recursividad 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 indirectamente recurrente, mientras que desde el punto de vista de g solo, g es indirectamente recurrente, mientras que desde el Desde el punto de vista de ambos, f y g son mutuamente recurrentes entre sí. De manera similar, un conjunto de tres o más funciones que se llaman entre sí puede denominarse conjunto de funciones mutuamente recursivas.
Matemáticamente, un conjunto de funciones mutuamente recursivas son recursivas primitivas , lo que se puede demostrar mediante recursividad de curso de valores , construyendo una función única F que enumere los valores de la función recursiva individual en orden: y reescribiendo la recursividad mutua como una recursividad primitiva. .
Cualquier recursividad mutua entre dos procedimientos se puede convertir en recursividad 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 la duplicación de código. En términos de la pila de llamadas, dos procedimientos mutuamente recursivos producen una pila ABABAB..., y al incluir B en A se obtiene la recursividad directa (AB)(AB)(AB)...
Alternativamente, se puede fusionar cualquier número de procedimientos en un único procedimiento que tome como argumento un registro variante (o tipo de datos algebraicos ) que represente la selección de un procedimiento y sus argumentos; Luego, el procedimiento combinado envía su argumento para ejecutar el código correspondiente y utiliza la recursividad directa para llamarse a sí mismo según corresponda. Esto puede verse como una aplicación limitada de la desfuncionalización . [10] Esta traducción puede ser útil cuando cualquiera de los procedimientos mutuamente recursivos puede ser llamado mediante código externo, por lo que no hay ningún caso obvio para insertar un procedimiento en el otro. Luego, dicho código debe modificarse para que las llamadas a procedimientos se realicen agrupando argumentos en un registro variante como se describe; alternativamente, se pueden utilizar procedimientos envolventes para esta tarea.
