Recursividad mutua

En matemáticas y programación, la recursividad mutua es un tipo de recursividad en la que dos objetos matemáticos o de programa, como funciones o tipos de datos, se definen en términos mutuos [1] . La recursividad mutua es común en la programación funcional y en algunas áreas problemáticas, como el método de descenso recursivo , donde los tipos de datos son naturalmente recursivos entre sí, lo que no es común en otros campos.

Ejemplos

Tipos de datos

El ejemplo más importante de datos que se pueden definir mediante la recursividad mutua es un árbol , que se puede definir en términos de un bosque (una lista de árboles). En forma simbólica:

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

El bosque f consiste en una lista de árboles, mientras que el árbol t consiste en un par - valor v y bosque f (hijos). Esta definición es elegante y fácil de usar porque el árbol se expresa en términos simples: una lista de un tipo y un par de dos tipos. Este tipo de datos es adecuado para muchos algoritmos de árbol que procesan valores de una manera y manejan la ramificación de otra manera.

Esta definición mutuamente recursiva se puede convertir en una sola definición recursiva utilizando la definición de bosque integrada: t: v [t[1], ..., t[k]]. El árbol t es un par: el valor v y una lista de árboles (hijos). Esta definición es más compacta, pero no todo es puro aquí: un árbol es un par: un valor de un tipo y una lista de otro tipo, lo que requerirá que se desarrolle la definición anterior.

En Standard ML , los tipos de datos de árboles y bosques se pueden definir de manera recursiva entre sí de la siguiente manera, si se permiten árboles vacíos [2] :

tipo de datos ' un árbol = Vacío | Nodo de ' a * ' a forest y ' a forest = Nil | Contras de ' un árbol * ' un bosque

Funciones de la computadora

Así como los algoritmos sobre tipos de datos recursivos pueden definirse mediante funciones recursivas, los algoritmos sobre estructuras de datos mutuamente recursivas pueden definirse naturalmente mediante funciones mutuamente recursivas. Los ejemplos bien conocidos incluyen algoritmos de árbol y el método de descenso recursivo . Como en el caso de la recursión directa, la optimización de recursión de cola es necesaria si la profundidad de recursión es grande o no está limitada en absoluto. Tenga en cuenta que la optimización de recursión de cola, en general (si la función llamada no es la misma que la función original, como en la recursión de cola) puede ser más difícil de implementar que en el caso de la optimización de recursión de cola, y una implementación eficiente de la recursión de cola mutua Es posible que no esté disponible en idiomas que optimicen solo las llamadas de cola. En lenguajes como Pascal , que requieren definiciones de objetos antes de que se pueda usar un objeto, las funciones mutuamente recursivas requieren una declaración directa .

Al igual que con las funciones recursivas directas, las funciones contenedoras con funciones mutuamente recursivas definidas como funciones anidadas el alcance pueden ser útiles si se admiten. Esto es particularmente útil para compartir datos entre múltiples funciones sin pasar parámetros.

Ejemplos básicos

Un ejemplo estándar de recursividad mutua, que es un truco ciertamente artificial, determina si un número es par o no definiendo dos funciones separadas que se llaman entre sí y reducen el número en cada llamada [3] . En C:

bool is_even ( sin firmar int n ) { si ( norte == 0 ) devolver verdadero ; más volver es_impar ( n - 1 ); } bool is_odd ( sin firmar int n ) { si ( norte == 0 ) devolver falso ; más volver es_par ( n - 1 ); }

Estas funciones se basan en la observación de que la pregunta "¿4 es par?" es equivalente a la pregunta "¿3 es impar?", que a su vez es equivalente a la pregunta "2 es par", y así sucesivamente hasta 0. El ejemplo muestra la recursión de unidades mutuas , que puede ser fácilmente reemplazada por una círculo. En este ejemplo, las llamadas de recurrencia mutua son llamadas de cola y es deseable optimizar las llamadas de cola para que la ejecución se produzca en un espacio de pila constante. En C, las funciones requerirán espacio de pila O ( n ) a menos que se usen saltos (goto) en lugar de llamadas a funciones [4] . El ejemplo se puede convertir en una sola función recursiva is_even. En este caso is_odd, se puede usar en línea y llamará is_even, pero is_evensolo se llamará a sí mismo.

Un ejemplo de una clase más general de ejemplos, el algoritmo de árbol, se puede descomponer en una operación de valor y una operación de rama, y ​​luego se puede dividir en dos funciones mutuamente recursivas, una de las funciones opera en el árbol y llama a la función de bosque , el segundo trabaja con el bosque y llama a la función del árbol para cada elemento del bosque. En lenguaje Python:

def f_tree ( árbol ): f_value ( árbol . valor ) f_forest ( árbol . niños ) def f_forest ( bosque ): para árbol en bosque : f_tree ( árbol )

En este caso, la función de árbol llama a la función de bosque usando una sola recursividad, pero la función de bosque usa múltiples recursiones en el árbol .

Utilizando los tipos de datos descritos anteriormente en Standard ML , el tamaño del árbol (número de aristas) se puede calcular mediante las siguientes funciones mutuamente recursivas [5] :

diversión size_tree Vacío = 0 | size_tree ( Nodo (_, f )) = 1 + size_forest f y size_forest Nil = 0 | tamaño_bosque ( Contras ( t , f' )) = tamaño_árbol t + tamaño_bosque f'

Un ejemplo de esquema más detallado que cuenta el número de hojas en un árbol [6] :

( definir ( contar-hojas del árbol ) ( if ( hoja? árbol ) 1 ( contar-hojas-en-el-bosque ( hijos del árbol )))) ( define ( contar-hojas-en-el-bosque bosque ) ( if ( nulo? bosque ) 0 ( + ( contar-hojas ( coche bosque )) ( contar-hojas-en-el-bosque ( cdr bosque )))))

Estos ejemplos se reducen fácilmente a una sola función recursiva incorporando la función de bosque en la función de árbol, lo que a menudo se hace en la práctica.

Ejemplos más avanzados

Ejemplos más complejos son los ejemplos de descendencia recursiva , que se pueden implementar de forma natural dando una función para cada regla generativa de la gramática, que luego se llaman recursivamente entre sí. En general, estas serán múltiples recursiones, cuando las reglas de generación combinan varias reglas. Esto se puede hacer sin recurrencia mutua, teniendo funciones separadas para cada regla de generación, pero llamando a una función de control o procesando toda la gramática en una función.

La recursión mutua también se puede utilizar para implementar una máquina de estado con una función para cada estado y una sola recursión por cambio de estado. Esto requiere una optimización de recursión de cola si el número de estados es grande o ilimitado. Este enfoque se puede utilizar como una forma simple de multitarea cooperativa . Un enfoque similar a la multitarea utiliza corrutinas que se llaman entre sí, donde en lugar de ser interrumpido llamando a otro procedimiento, una corrutina llama a otra, pero no se interrumpe, sino que continúa la ejecución cuando regresa la corrutina llamada. Esto permite que las corrutinas individuales guarden el estado sin tener que pasar parámetros o guardar variables compartidas.

También hay algoritmos que naturalmente tienen dos fases, como minimax (mínimo y máximo), y estos se pueden implementar creando una función mutuamente recursiva separada para cada fase, aunque también se pueden combinar en una sola función recursiva directa.

Funciones matemáticas

En matemáticas , las secuencias de Hofstadter masculina y femenina son un ejemplo de un par de secuencias de números enteros que son recursivas entre sí.

Los fractales se pueden calcular (con la precisión requerida) usando funciones recursivas. A veces, esto se puede hacer de manera más elegante con números recursivos entre sí. La curva de Sierpinski es un buen ejemplo.

Prevalencia

La recursividad mutua se usa ampliamente en la programación funcional y, a menudo, se usa en programas escritos en Lisp , Scheme , ML y otros lenguajes similares . En lenguajes como Prolog , la recursividad mutua es casi inevitable.

Algunos estilos de programación desalientan la recurrencia mutua, argumentando que es difícil distinguir entre las condiciones que devolverán una respuesta de las condiciones que harán que el código se repita (ejecutar para siempre sin devolver una respuesta). Peter Norvig señaló el patrón de desarrollo que debe evitarse de todos modos. Él afirma [7] :

Si tiene dos funciones mutuamente recursivas que cambian el estado de un objeto, intente mover casi toda la funcionalidad a una de esas funciones. De lo contrario, es más probable que termine con la duplicación de código.

Terminología

La recursividad mutua también se conoce como recursividad indirecta , a diferencia de la recursividad directa cuando una función se llama a sí misma directamente. Esta es solo una diferencia en el énfasis, no una diferencia en el enfoque: la "recurrencia indirecta" enfatiza el uso de una función individual, mientras que la "recurrencia mutua" enfatiza el uso de un conjunto de funciones en lugar de una sola función individual. Por ejemplo, si f se llama a sí mismo, es una recursividad directa. Si 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 tiene recursividad indirecta. Desde el punto de vista de la función g , también tiene recursividad indirecta. Pero desde el punto de vista del conjunto de funciones f y g , tenemos recurrencia mutua entre sí. De manera similar, un conjunto de tres o más funciones pueden llamarse mutuamente.

Reducción a recursividad directa

Matemáticamente, un conjunto de funciones mutuamente recursivas son primitivamente recursivas , lo que se puede demostrar usando recursividad hacia atrás [8] , para lo cual se construye una función F que enumera los valores de las funciones recursivas individuales en orden intercalado: y recursividad mutua se reescribe como una recursividad primitiva.

Cualquier recursión mutua entre dos procedimientos puede reducirse a recursión directa insertando el código de un procedimiento dentro del otro. Si solo hay un lugar donde el procedimiento llama a otro, esto se puede hacer directamente, pero si hay varios de esos lugares, es posible que se requiera la duplicación de código. En términos de uso de la pila, dos procedimientos mutuamente recursivos llenan la pila con una secuencia de llamadas ABABAB... y el procedimiento incrustado B en A da como resultado una recursión directa (AB)(AB)(AB)...

Alternativamente, cualquier número de procedimientos se puede fusionar en un solo procedimiento que toma como argumento una unión etiquetada (o tipo de datos algebraico ) que almacena información sobre el procedimiento que se llama y sus argumentos. El procedimiento ensamblado selecciona una rama en función de los argumentos y ejecuta el código apropiado, luego usa la recursividad directa para llamarse a sí mismo con los argumentos apropiados. Este enfoque puede verse como una versión truncada de la exclusión de funciones [9] . Esta combinación de funciones puede ser útil cuando un código externo puede llamar a algunas funciones, de modo que no es posible anidar un procedimiento dentro de otro. Dicho código debe convertirse para que las llamadas a procedimientos se realicen concatenando argumentos en una "unión etiquetada" como se describe anteriormente. Otra opción es utilizar un procedimiento de envoltura.

Véase también

Notas

  1. ↑ Rubio-Sánchez, Urquiza-Fuentes, Pareja-Flores, 2008 , p. 235-239.
  2. ↑ Harper, 2005 , " Tipos de fecha ".
  3. ↑ Hutton, 2007 , 6.5 Recurrencia mutua, págs. 53–55 .
  4. ↑ " Mutual Tail-Recursion Archivado el 10 de abril de 2016 en Wayback Machine " y " Tail-Recursive Functions Archivado el 10 de abril de 2016 en Wayback Machine ", Un tutorial sobre funciones de programación en ATS Archivado el 27 de diciembre de 2017 en Wayback Machine . Hongwei Xi, 2010
  5. ↑ Harper, 2005 , " Tipos de datos ".
  6. ↑ Harvey, Wright, 1999 , V. Abstraction: 18. Trees: Mutual Recursion, págs. 310–313 .
  7. ↑ Resolviendo cada rompecabezas de Sudoku . Consultado el 13 de enero de 2017. Archivado desde el original el 15 de noviembre de 2020.
  8. ↑ " recursividad mutua Archivado el 21 de junio de 2018 en Wayback Machine " PlanetMath
  9. ↑ Reynolds, John (agosto de 1972). "Intérpretes de definición para lenguajes de programación de orden superior" (PDF) . Actas de la Conferencia Anual de la ACM . Boston, Massachusetts. páginas. 717-740. Archivado el 29 de junio de 2011 en Wayback Machine .

Literatura

  • Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes,Cristóbal Pareja-Flores. Boletín ACM SIGCSE. - ACM, 2008. - T. 40. - S. 235-239.
  • Roberto Harper. Programación en Standard ML (Working Draft del 17 de MAYO de 2005). — Universidad Carnegie Mellon, 2005.
  • Brian HarveyMatthew Wright. Esquema simple: introducción a la informática. - MIT Press, 1999. - ISBN 978-0-26208281-5 .
  • Graham Hutton. Programación en Haskell. - Cambridge University Press, 2007. - ISBN 978-0-52169269-4 .

Enlaces