Recursividad mutua

En matemáticas e informática, la recurrencia mutua es una forma de recurrencia en la que dos objetos matemáticos o computacionales, como funciones o tipos de datos, se definen uno en relación con el otro. La recursión mutua es muy común en la programación funcional y en algunos dominios de problemas, como los analizadores descendentes recursivos, donde los tipos de datos son naturalmente recursivos entre sí.

Ejemplos

Tipos de datos

El ejemplo básico más importante de un tipo de datos que se puede definir mediante recursividad mutua es un árbol, que se puede definir de forma recursiva mutua en términos de un bosque (una lista de árboles). Simbólicamente:

f: [t[1],..., t[k]
t: v f

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 < i>f (sus hijos). Esta definición es elegante y fácil de trabajar de manera abstracta (como cuando se prueban teoremas sobre las propiedades de los á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 los árboles, que consisten en hacer una cosa con el valor y otra cosa con los niños.

Esta definición recursiva mutua se puede convertir en una definición recursiva simple 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 consiste en un par de un tipo y una lista de otro, que requieren ser desenredados para probar los resultados.

En Standard ML, los tipos de datos de árbol y bosque se pueden definir de forma recursiva mutuamente de la siguiente manera, lo que permite árboles vacíos:

datatype 'a árbol = Vacío Silencio Node de 'a * 'a bosquey 'a bosque = Nil Silencio Cons de 'a árbol * 'a bosque

Funciones de la computadora

Así como los algoritmos en tipos de datos recursivos pueden ser dados naturalmente por funciones recursivas, los algoritmos en estructuras de datos mutuamente recursivas pueden ser dados naturalmente por funciones mutuamente recursivas. Los ejemplos comunes incluyen algoritmos en árboles y analizadores de descenso recursivos. Al igual que con la recursividad directa, la optimización de la llamada final es necesaria si la profundidad de la recursividad es grande o ilimitada, como el 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 la 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 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 recursivas directas, una función contenedora puede ser útil, con las funciones mutuamente recursivas definidas como funciones anidadas dentro de su alcance si es compatible. Esto es particularmente útil para compartir el estado en un conjunto de funciones sin tener que pasar parámetros entre ellas.

Ejemplos básicos

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. Cª:

bool ################################################################################################################################################################################################################################################################()no firmado int n) {} si ()n == 0) retorno verdadero; más retorno is_odd()n - 1);}bool is_odd()no firmado int n) {} si ()n == 0) retorno falso; más retorno ################################################################################################################################################################################################################################################################()n - 1);}

Estas funciones se basan en la observación de que la pregunta ¿es 4 par? es equivalente a ¿es 3 impar?, que a su vez es equivalente a es 2 even?, y así sucesivamente hasta 0. Este ejemplo es una recursividad única mutua, y podría reemplazarse fácilmente por iteración. En este ejemplo, las llamadas mutuamente recursivas son llamadas de cola, y sería necesaria la optimización de llamadas de cola para ejecutarlas en un espacio de pila constante. En C, esto ocuparía espacio de pila O(n), a menos que se reescriba para usar saltos en lugar de llamadas. Esto podría reducirse a una única función recursiva is_even. En ese caso, is_odd, que podría estar en línea, llamaría a is_even, pero is_even solo se llamaría a sí mismo.

Como una clase más general de ejemplos, un algoritmo en un árbol puede descomponerse en su comportamiento en un valor y su comportamiento en niños, y puede dividirse en dos funciones mutuamente recursivas, una que especifica el comportamiento en un árbol, llamando a la función de bosque para el bosque de niños, y uno especificando 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.niños)def f_forest()bosque) - Ninguno: para árbol dentro bosque: F_tree()árbol)

En este caso, la función de árbol llama a la función de bosque por recursión única, pero la función de bosque llama a la función de árbol por recursión múltiple.

Usando el tipo de datos de ML estándar anterior, el tamaño de un árbol (número de nodos) se puede calcular a través de las siguientes funciones mutuamente recursivas:

diversión size_tree Vacío = 0 Silencio size_tree ()Node (_ f) = 1 + size_forest fy size_forest Nil = 0 Silencio size_forest ()Cons ()t, f ') = size_tree t + size_forest f '

Un ejemplo más detallado en Scheme, contando las hojas de un árbol:

()definir ()Cuentos árbol) ()si ()hoja? árbol) 1 ()conteo-leaves-en-forest ()niños árbol)))()definir ()conteo-leaves-en-forest bosque) ()si ()null? bosque) 0 ()+ ()Cuentos ()coche bosque) ()conteo-leaves-en-forest ()cdr bosque))))

Estos ejemplos se reducen fácilmente a una sola función recursiva integrando 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 elementos secundarios dentro de uno función, en lugar de dividirlos en dos funciones separadas.

Ejemplos avanzados

Un ejemplo más complicado es el de los analizadores descendentes recursivos, que se pueden implementar naturalmente al tener una función para cada regla de producción de una gramática, que luego recurren mutuamente; en general, esto será una recursión múltiple, ya que las reglas de producción generalmente combinan múltiples partes. Esto también se puede hacer sin recurrencia mutua, por ejemplo, manteniendo funciones separadas para cada regla de producción, pero haciéndolas llamar por una sola 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 recursividad única en estado cambiante; esto requiere la optimización de la llamada final 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 usar corrutinas que se llamen entre sí, donde en lugar de terminar llamando a otra rutina, una corrutina cede a otra pero no termina, y luego reanuda la ejecución cuando se le devuelve. Esto permite que las corrutinas individuales mantengan el estado, sin necesidad de que se pasen por parámetros o se almacenen en variables compartidas.

También hay algunos algoritmos que naturalmente tienen dos fases, como minimax (mín. y máx.), que se pueden implementar al tener cada fase en una función separada con recursividad mutua, aunque también se pueden combinar en una sola función con recursión directa.

Funciones matemáticas

En matemáticas, las sucesiones femenina y masculina de Hofstadter son un ejemplo de un par de sucesiones 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 a través de funciones mutuamente recursivas; la curva de Sierpiński es un buen ejemplo.

Prevalencia

La recursión mutua es muy común en la programación funcional y, a menudo, se usa para programas escritos en LISP, Scheme, ML y lenguajes de programación similares. Por ejemplo, Abelson y Sussman describen cómo se puede usar un evaluador metacircular para implementar LISP con un ciclo de aplicación de evaluación. En lenguajes como Prolog, la recursividad mutua es casi inevitable.

Algunos estilos de programación desalientan la recurrencia mutua, alegando que puede ser 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 desalienta el uso por completo, afirmando:

Si usted tiene dos funciones mutuamente recursivas que alteran el estado de un objeto, trate de mover casi toda la funcionalidad en sólo una de las funciones. De lo contrario probablemente terminará duplicando el código.

Terminología

La recursividad mutua también se conoce como recursividad indirecta, en contraste con la recursividad directa, donde una sola función se llama a sí misma directamente. Esto es simplemente una diferencia de énfasis, no una noción diferente: "recursión indirecta" enfatiza una función individual, mientras que la "recurrencia mutua" enfatiza el conjunto de funciones y no destaca 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 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 llamarse un conjunto de funciones mutuamente recursivas.

Conversión a recursividad directa

Matemáticamente, un conjunto de funciones mutuamente recursivas son primitivas recursivas, que pueden ser probadas por la recursión de los valores, construyendo una sola función F que enumera los valores de la función recursiva individual en orden: ${displaystyle F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),dots}$ y reescribir la repetició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. 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 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 algebraico) 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 la recursividad directa para llamarse a sí mismo según corresponda. Esto puede verse como una aplicación limitada de la desfuncionalización. Esta traducción puede ser útil cuando cualquiera de los procedimientos mutuamente recursivos puede ser llamado por un código externo, por lo que no hay un 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 de variante como se describe; alternativamente, se pueden utilizar procedimientos de envoltorio para esta tarea.