Hispanopedia Wiki
Articulo de referencia

Recursión mutua

En matemáticas e informática , la recursión mutua es una forma de recursión en la que dos o más objetos matemáticos o computacionales, como funciones o tipos de datos, se define...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas e informática , la recursión mutua es una forma de recursión en la que dos o más objetos matemáticos o computacionales, como funciones o tipos de datos, se definen en términos unos de otros. [ 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 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 dato que puede definirse mediante recursión mutua es un árbol , que puede definirse de forma recursiva 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 formado por un valor v y un bosque f (sus hijos). Esta definición es elegante y fácil de usar de forma abstracta (por ejemplo, al demostrar teoremas sobre propiedades de árboles), ya que expresa un árbol en términos sencillos: una lista de un tipo y un par de dos tipos. Además, coincide con muchos algoritmos sobre árboles, que consisten en realizar una operación con el valor y otra con los hijos.

Esta definición mutuamente recursiva se puede convertir en una definición recursiva simple insertando en línea la definición de un bosque:

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

Un árbol t consta de un par formado por un valor v y una lista de árboles (sus hijos). Esta definición es más compacta, pero algo más compleja: un árbol consta de un par de un tipo y una lista de otro, que requieren ser desentrañados para demostrar resultados sobre él.

En Standard ML , los tipos de datos de árbol y bosque se pueden definir recursivamente de forma mutua como sigue, permitiendo árboles vacíos: [ 2 ]

tipo de datos 'un árbol = Vacío | Nodo de 'un * 'un bosque y 'un bosque = Nulo | Cons de 'un árbol * 'un bosque

Funciones de la computadora

Así 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. Ejemplos comunes incluyen algoritmos sobre árboles y analizadores sintácticos descendentes 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 cuando se usa la recursión mutua para la 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 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 en lenguajes que solo optimizan llamadas recursivas de cola. En lenguajes como Pascal que requieren declaración antes de su uso, las funciones mutuamente recursivas requieren declaración anticipada , ya que no se puede evitar una referencia anticipada al definirlas.

Al igual que con las funciones recursivas directas, puede resultar útil una función contenedora , donde las funciones recursivas mutuas se definen como funciones anidadas dentro de su ámbito, si esta funcionalidad lo permite. Esto es especialmente útil para compartir el estado entre varias funciones sin necesidad de pasar parámetros entre ellas.

Ejemplos básicos

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 ) { if ( n == 0 ) { return true ; } else { return is_odd ( n - 1 ); } }bool is_odd ( unsigned int n ) { if ( n == 0 ) { return false ; } else { return is_even ( n - 1 ); } }

Estas funciones se basan en la observación de que la pregunta es ¿4 par? es equivalente a ¿3 impar?, que a su vez es equivalente a ¿2 par?, y así sucesivamente hasta 0. Este ejemplo es una recursión simple mutua , y podría reemplazarse fácilmente por una 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 ejecutarse en un espacio de pila constante. En C, esto tomaría un espacio de pila O ( n ), 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 ser inline, llamaría a is_even, pero is_evensolo se llamaría a sí misma.

Como ejemplo más general, un algoritmo en un árbol se puede descomponer en su comportamiento sobre un valor y su comportamiento sobre los hijos, y se puede dividir en dos funciones mutuamente recursivas: una que especifica el comportamiento en un árbol, llamando a la función `forest` para el bosque de hijos, y otra que especifica el comportamiento en un bosque, llamando a la función `tree` para el árbol en el bosque. En Python:

def f_tree ( árbol : Árbol ) -> Ninguno : f_value ( árbol . valor ) f_forest ( árbol . hijos )def f_forest ( bosque : Bosque ) -> Ninguno : para árbol en bosque : f_tree ( árbol )

En este caso, la función de árbol llama a la función de bosque mediante una sola recursión, pero la función de bosque llama a la función de árbol mediante múltiples recursiones .

Utilizando el tipo de datos ML estándar anterior, el tamaño de un árbol (número de nodos) se puede calcular mediante las siguientes funciones mutuamente recursivas: [ 5 ]

fun size_tree Empty = 0 | size_tree ( Node (_, f )) = 1 + size_forest f and size_forest Nil = 0 | size_forest ( Cons ( t , f' )) = size_tree t + size_forest f'

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

( define ( count-leafs tree ) ( if ( leaf? tree ) 1 ( count-leafs-in-forest ( children tree ))))( define ( count-leaves-in-forest forest ) ( if ( null? forest ) 0 ( + ( count-leaves ( car forest )) ( count-leaves-in-forest ( cdr forest )))))

Estos ejemplos se reducen fácilmente a una única función recursiva al integrar la función de bosque en la función de árbol, lo cual se hace comúnmente en la práctica: las funciones recursivas directas que operan sobre árboles procesan secuencialmente el valor del nodo y recurren sobre los hijos dentro de una misma función, en lugar de dividirlas en dos funciones separadas.

Ejemplos avanzados

Un ejemplo más complejo lo constituyen los analizadores sintácticos descendentes recursivos , que pueden implementarse de forma natural mediante una función para cada regla de producción de una gramática, las cuales se recurren mutuamente; esto generalmente implica recursión múltiple, ya que las reglas de producción suelen combinar varias partes. Esto también puede lograrse sin recursión mutua, por ejemplo, manteniendo funciones separadas para cada regla de producción, pero haciéndolas llamar por una única función controladora, o bien, incluyendo toda la gramática en una sola 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 sola recursión al cambiar de estado; esto requiere optimización de llamadas de cola si el número de cambios de estado es grande o ilimitado. Esto puede usarse como una forma simple de multitarea cooperativa . Un enfoque similar a la multitarea consiste en usar 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 existen algunos algoritmos que, de forma natural, constan de dos fases, como el minimax (mínimo y máximo), que pueden implementarse mediante la inclusión de cada fase en una función separada con recursión mutua, aunque también pueden combinarse en una única función con recursión directa.

Funciones matemáticas

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 pueden calcularse (hasta una resolución determinada) mediante funciones recursivas. En ocasiones, esto puede hacerse de forma más elegante mediante funciones mutuamente recursivas; la curva de Sierpiński es un buen ejemplo.

Predominio

La recursión mutua es muy común en la programación funcional y se usa frecuentemente en 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 eval-apply. [ 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 ejecutara indefinidamente sin producir una respuesta. Peter Norvig señala un patrón de diseño que desaconseja su uso por completo, afirmando: [ 8 ]

Si tienes dos funciones recursivas que modifican el estado de un objeto, intenta concentrar casi toda la funcionalidad en una sola función. De lo contrario, probablemente terminarás duplicando código.

Terminología

La recursión mutua, también conocida como recursión indirecta , contrasta con la recursión directa , donde una sola función se llama a sí misma directamente. Se trata simplemente de una diferencia de énfasis, no de un concepto distinto: la "recursión indirecta" se centra en una función individual, mientras que la "recursión mutua" se centra en el conjunto de funciones y no en una función específica. Por ejemplo, si f se llama a sí misma, se trata de recursión directa. Si, en cambio, f llama a g y luego g llama a f, que a su vez llama a g de nuevo, desde el punto de vista de f , f es recursiva indirecta; desde el punto de vista de g , g es recursiva indirecta; y desde el punto de vista de ambas, f y g son recursivas entre sí. De forma similar, un conjunto de tres o más funciones que se llaman entre sí puede denominarse conjunto de funciones recursivas mutuas.

Conversión a recursión directa

Matemáticamente, un conjunto de funciones mutuamente recursivas son recursivas primitivas , lo cual se puede demostrar mediante la recursión de curso de valores , construyendo una única función F que enumera los valores de las funciones recursivas individuales en orden:F=F1(0),F2(0),F1(1),F2(1),…,{\displaystyle F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,}y reescribiendo la recursión mutua como una recursión primitiva.

La recursión mutua simple 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 punto donde un procedimiento llama al otro, esto es sencillo; si hay varios, puede implicar duplicación de código. En términos de la pila de llamadas, dos procedimientos mutuamente recursivos generan una pila ABABAB..., e insertar B en A genera la recursión directa (AB)(AB)(AB)...

De manera más general, cualquier número de procedimientos se puede fusionar en un solo procedimiento que toma como argumento un registro variante (o tipo de dato 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 recursión directa para llamar a sí mismo según sea apropiado. Esto puede verse como una aplicación limitada de la defuncionalización . [ 10 ] Esta traducción puede ser útil cuando cualquiera de los procedimientos mutuamente recursivos puede ser llamado por código externo, por lo que no hay un caso obvio para insertar un procedimiento en línea en el otro. Dicho código entonces necesita ser modificado para que las llamadas a procedimientos se realicen agrupando argumentos en un registro variante como se describió; alternativamente, se pueden usar procedimientos envoltorio para esta tarea.

Véase también

Referencias

  1. ↑ Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes, Cristóbal Pareja-Flores (2002), 'Una introducción sencilla a la recursión mutua', Actas de la 13.ª conferencia anual sobre innovación y tecnología en la enseñanza de la informática, 30 de junio - 2 de julio de 2008, Madrid, España.
  2. ↑ Harper 2000 , " Tipos de fecha ".
  3. ↑ Hutton 2007 , 6.5 Recursión mutua, págs. 53–55 .
  4. ↑ " Recursión de cola mutua " y " Funciones recursivas de cola ", Tutorial sobre características de programación en ATS , Hongwei Xi, 2010
  5. ↑ Harper 2000 , " Tipos de datos ".
  6. ↑ Harvey y Wright 1999 , V. Abstracción: 18. Árboles: Recursión mutua, págs. 310–313 .
  7. ↑ Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie (1996). Estructura e interpretación de programas informáticos (PDF) . Londres, Inglaterra: The MIT Press. pág.  492. ISBN 978-0262510875.
  8. ↑ Resolviendo todos los rompecabezas de Sudoku
  9. ↑ Sobre la conversión de recursión indirecta a directa por Owen Kaser, CR Ramakrishnan y Shaunak Pawagi en la Universidad Estatal de Nueva York, Stony Brook (1993)
  10. ↑ Reynolds, John (agosto de 1972). "Intérpretes definicionales para lenguajes de programación de orden superior" (PDF) . Actas de la Conferencia Anual de la ACM . Boston, Massachusetts. págs. 717–740 . 
  • Harper, Robert (2000), Programación en Standard ML
  • Harvey, Brian; Wright, Matthew (1999). Simply Scheme: Introducción a la informática . MIT Press. ISBN 978-0-26208281-5.
  • Hutton, Graham (2007). Programación en Haskell . Cambridge University Press. ISBN 978-0-52169269-4.