En matemáticas e informática , la recursividad mutua es una forma de recursión en la que dos objetos matemáticos o computacionales, como funciones o tipos de datos, se definen en términos de cada uno. [1] La recursividad 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 de
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 recursivamente mutuamente 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 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 á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 al incluir la definición de 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 desordenada: un árbol consta de un par de un tipo y una lista de otro, que requieren desenredarse para probar los resultados.
En el ML estándar , los tipos de datos de árboles y bosques 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 'un bosque = Nil | Contras 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 recursivas pueden ser dados naturalmente por funciones recursivas entre sí. 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 de cola es necesaria si la profundidad de recursión es grande o ilimitada, como el uso de recursividad mutua para realizar múltiples tareas. Tenga en cuenta que la optimización de la llamada 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 recursividad de cola mutua puede estar ausente en lenguajes que solo optimizan las llamadas recursivas de cola. En lenguajes como Pascal que requieren declaración antes de su uso, las funciones recursivas entre sí requieren 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 recursivas mutuamente definidas como funciones anidadas dentro de su alcance si se admite. 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 al definir 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 ) return true ; de lo contrario, devuelve is_odd ( n - 1 ); }bool is_odd ( unsigned int n ) { if ( n == 0 ) return false ; si no, return is_even ( 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 2 par? , y así sucesivamente hasta 0. Este ejemplo es recursividad única mutua y podría reemplazarse fácilmente por iteración. En este ejemplo, las llamadas recursivas entre sí son llamadas de cola , y la optimización de la llamada de cola sería necesaria para ejecutarse en un espacio de pila constante. En C, esto tomaría O ( n ) espacio en la pila, a menos que se reescribiera para usar saltos en lugar de llamadas. [4] Esto podría reducirse a una sola función recursiva is_even
. En ese caso, lo is_odd
que podría estar insertado, llamarí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 se puede descomponer en su comportamiento en un valor y su comportamiento en niños, y se puede dividir en dos funciones recursivas mutuamente, una que especifica el comportamiento en un árbol, llamando al bosque función para el bosque de niños, y una 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 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 .
Con 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 recursivas entre sí: [5]
fun 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 ( contar-hojas de árbol ) ( si ( ¿hoja? árbol ) 1 ( contar-hojas-en-bosque ( árbol de niños ))))( Definir ( recuento de hojas-en-bosque bosque ) ( si ( nula? Bosque ) 0 ( + ( recuento de hojas ( coche bosque )) ( recuento de hojas-en-bosque ( CDR bosque )))))
Estos ejemplos se reducen fácilmente a una sola función recursiva insertando 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, que dividirlos en dos funciones separadas.
Ejemplos avanzados
Un ejemplo más complicado lo dan los analizadores sintácticos descendentes recursivos , que pueden implementarse naturalmente al tener una función para cada regla de producción de una gramática, que luego se recursan mutuamente; en general, esto será una recursividad múltiple, ya que las reglas de producción generalmente combinan varias partes. Esto también se puede hacer sin recursividad mutua, por ejemplo, aún teniendo funciones separadas para cada regla de producción, pero llamándolas por 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 la optimización de la llamada 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 usar corrutinas que se llaman 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 pasarlas por parámetros o almacenarlas en variables compartidas.
También hay algunos algoritmos que naturalmente tienen dos fases, como minimax (min y max), 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 recursividad directa.
Funciones matematicas
En matemáticas, las secuencias femeninas y masculinas de Hofstadter son un ejemplo de un par de secuencias enteras definidas de manera recursiva mutua.
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 recursivas entre sí; la curva de Sierpiński es un buen ejemplo.
Predominio
La recursividad 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 utilizar un evaluador meta-circular para implementar LISP con un ciclo de evaluación y aplicación. [7] En lenguajes como Prolog , la recursividad mutua es casi inevitable.
Algunos estilos de programación desalientan 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 desalienta el uso por completo, afirmando: [8]
Si tiene dos funciones recursivas entre sí que alteran el estado de un objeto, intente mover casi toda la funcionalidad a una sola 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: la "recursividad indirecta" enfatiza una función individual, mientras que la "recursividad 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 gy luego g llama a f, que a su vez vuelve a llamar a g , desde el punto de vista de f solo, f está recidivando indirectamente, mientras que desde el punto de vista de g solo, g está recidivando indirectamente, mientras que desde punto de vista de ambos, f y g están recursivamente mutuamente el uno del otro. De manera similar, un conjunto de tres o más funciones que se llaman entre sí puede denominarse un conjunto de funciones recursivas entre sí.
Conversión a recursividad directa
Matemáticamente, un conjunto de funciones recursivas entre sí son recursivas primitivas , lo que puede probarse mediante la recursividad del curso de valores , [9] construyendo una única función F que enumera los valores de la función recursiva individual en orden: y reescribir la recursividad mutua como recursividad primitiva.
Cualquier recursividad mutua entre dos procedimientos se puede convertir en recursividad directa insertando el código de un procedimiento en el otro. [10] 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 recursivos entre sí producen una pila ABABAB ..., y la inserción de B en A produce la recursividad directa (AB) (AB) (AB) ...
Alternativamente, cualquier número de procedimientos se puede fusionar en un solo procedimiento que toma como argumento un registro variante (o tipo de datos algebraicos ) que representa la selección de un procedimiento y sus argumentos; el procedimiento combinado luego envía su argumento para ejecutar el código correspondiente y usa la recursividad directa para llamar a self según corresponda. Esto puede verse como una aplicación limitada de la desfuncionalización . [11] Esta traducción puede ser útil cuando cualquiera de los procedimientos recursivos entre sí puede ser llamado por un 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 de envoltura para esta tarea.
Ver también
- Detección de ciclos (teoría de grafos)
- Recursión (informática)
- Dependencia circular
Referencias
- ^ Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes, Cristóbal Pareja-Flores (2002), 'A Gentle Introduction to Mutual Recursion', Actas de la XIII conferencia anual sobre innovación y tecnología en la educación informática, 30 de junio-2 de julio de 2008 , Madrid, España.
- ^ Harper 2000 , " Tipos de fecha ".
- ^ Hutton 2007 , 6.5 recursividad mutua, págs. 53–55 .
- ^ " Recursión de cola mutua " y " Funciones recursivas de cola ", un tutorial sobre funciones de programación en ATS , Hongwei Xi, 2010
- ^ Harper 2000 , " Tipos de datos ".
- ^ Harvey y Wright 1999 , V. Abstracción: 18. Árboles: recursividad mutua, págs. 310-313 .
- ^ Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie (1996). Estructura e interpretación de programas informáticos (PDF) . Londres, Inglaterra: The MIT Press. pag. 492. ISBN 978-0262510875.
- ^ Resolver todos los rompecabezas de Sudoku
- ^ " recursividad mutua ", PlanetMath
- ^ Sobre la conversión de la recursividad indirecta en directa por Owen Kaser, CR Ramakrishnan y Shaunak Pawagi en la Universidad Estatal de Nueva York, Stony Brook (1993)
- ^ Reynolds, John (agosto de 1972). "Intérpretes de definiciones para lenguajes de programación de orden superior" (PDF) . Actas de la Conferencia Anual de ACM . Boston, Massachusetts. págs. 717–740.
- Harper, Robert (2000), Programación en ML estándar
- Harvey, Brian; Wright, Matthew (1999). Simply Scheme: Introducción a la informática . Prensa del MIT. ISBN 978-0-26208281-5.
- Hutton, Graham (2007). Programación en Haskell . Prensa de la Universidad de Cambridge. ISBN 978-0-52169269-4.
enlaces externos
- Recursión mutua en Rosetta Code
- " Ejemplo que demuestra el buen uso de la recursividad mutua ", " ¿Hay algún ejemplo de recursión mutua? ", Stack Overflow