Recursión mutua

En matemáticas e informática, la recursión mutua es una forma de recursión donde dos objetos matemáticos o computacionales, como funciones o tipos de dato, son definidos uno en términos de otro.^[1] La recursión mutua es muy común en programación funcional y algunos problemas de dominio, como en analizadores sintácticos de recursión descendente donde los tipos de datos son mutuamente recursivos.

Ejemplos

Tipos de datos

El ejemplo más importante de un tipo de dato que se puede definir con una recursión mutua es un árbol, que puede ser definido mutua y recursivamente en términos de un conjunto de árboles.

Simbólicamente:

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

Un bosque f consiste en una lista de árboles, mientras que un árbol t consiste en un par de valores v y un sub-árbol f. Esta definición es ordenada y fácil para trabajar abstractamente (como cuando se prueban teoremas sobre las propiedades de los árboles), tal como se expresa un árbol en términos simples: una lista de un tipo y un par de dos tipos. Además, une muchos algoritmos de árboles, que consisten en hacer una operación con el valor, y otra cosa con los sub-árboles.

Esta definición mutuamente recursiva se puede convertir a una definición recursiva individual al delimitar la definición de conjunto de árboles:

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

Un árbol t consiste en 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 consiste en un par de un tipo y una lista de otro, que requieren desenmarañarse para probar los resultados aproximados.

En Stándar ML, el árbol y los tipos del bosque se pueden definir con recursión mutua de la siguiente manera, lo que permite árboles vacíos:

datatype 'a tree = Empty | Node of 'a * 'a forest
and 'a forest = Nil | Cons of 'a tree * 'a forest

Funciones de ordenador

Del mismo modo que los algoritmos en los tipos de datos recursivos pueden ser dados naturalmente por funciones recursivas, los algoritmos en las 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 recursión directa, la optimización de la cola de cola es necesaria si la profundidad de recursión es grande o ilimitada, como el uso de la recursión mutua para la multitarea. Tenga en cuenta que la optimización de llamadas finales 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 recursiva de cola, y por lo tanto una 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 idiomas como Pascal que requieren declaración antes del uso, las funciones mutuamente recursivas requieren la declaración directa, ya que una referencia directa no se puede evitar 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 esto es compatible. Esto es particularmente útil para compartir estados a través de un conjunto de funciones sin tener que pasar parámetros entre ellos.

Ejemplos básicos

Un ejemplo estándar de recursión mutua, el cual es ciertamente artificial: Determinar si un número no negativo es par o impar por definición dos funciones separadas que se llaman una a la otra, disminuyendo cada vez. 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);
}

Esas funciones son basadas en la observación de la pregunta "¿4 es par?" Esto es equivalente a "¿3 es impar?" Lo que a su vez equivale a preguntarnos si "¿2 es par?", y así sucesivamente hasta llegar a cero. Este ejemplo es una solo una mutua recursión, y podría establecerse fácilmente por interacción. En este ejemplo, la llamada mutuamente recursiva son colas de llamadas, las cuales para optimizarlas sería necesario ejecutar un espacio de pilas constante. En C, esto ocuparía O(n) de espacio de pilas, a menos que se reescriba la función usando saltos en vez de llamadas. Esto podría ser reducido por solo una función recursiva is_even. En ese caso, is_odd, que podría ser alineado, llamaría a is_even, pero is_even solo se llamaría a sí misma.

Una clase de ejemplo más general, un algoritmo de un árbol puede ser descompuesto dentro de su comportamiento en un valor y el comportamiento de los sub-árboles(children), y puede ser dividido dentro de dos funciones de mutua recursión. Una especificando el comportamiento en un árbol, llamando a la función forest para el conjunto de sub-árboles, y otra especificando el comportamiento de un conjunto de árboles, llamando a la función tree para el árbol del conjunto de árboles. En Python:

 def f_tree(tree):
     f_value(tree.value)
     f_forest(tree.children)

 def f_forest(forest):
     for tree in forest:
         f_tree(tree)

En este caso la función tree llama a la función forest por solo una recursión, mientras que la función forest llama a la función tree por recursión múltiple. Usando el tipo de datos Standard ML en el ejemplo anterior, el tamaño de un árbol (número de nodos) puede ser calculada por medio de las siguientes funciones recursivas:

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 Esquema, contando las hojas de un árbol:

(define (count-leaves tree)
  (if (leaf? tree)
      1
      (count-leaves-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 reducen fácilmente a una sola función recursiva mediante la adjunción de la función forest en la función tree, que es comúnmente puesto en práctica: las funciones directamente recursivas que operan en procesos secuenciales de árboles el valor del nodo y recursión en los sub-árboles dentro de una función en lugar de dividirlas dentro de dos funciones separadas.

Ejemplos avanzados

Un ejemplo más complicado es dado por un analizador descendente recursivo, el cual puede ser naturalmente implementado por una función por cada regla de producción de una gramática; eso en general será una recursión múltiple, como las reglas de producción generalmente combina múltiples partes. Eso puede ser hecho sin recursión múltiple, por ejemplo, incluso teniendo funciones separadas para cada regla de producción, pero teniéndolos llamados por una sola función controladora, o poniendo toda la gramática en una sola función.

La recursión mutua puede también implementar una máquina finita de estado, con una función por cada estado, y solo una recursión en cada cambio de estado; eso requiere colas de llamados de optimización, si el número de estados es largo o abundante. Eso puede ser usado como una simple cooperación de multitareas. Un enfoque similar de multitareas es por ejemplo usar cortinas, donde cada una llama a cada otra, en lugar de llamar a otra rutina cede el control a otra, pero no lo termina, y luego pasará a la ejecución cuando es cedido de regreso. Eso permite cortinas individuales para mantener el estado, sin necesidad de pasar por otros parámetros en variables compartidas.

Existen algunos algoritmos que naturalmente tienen dos fases, como minimax (min y máx), y esos pueden ser implementados teniendo cada fase en una función separada con recursión mutua, a pesar de que pueden también ser combinados dentro de una sola función con recursión directa.

Funciones matemáticas

En matemáticas, The Hofstadter Female and Male sequences son un ejemplo de un par de secuencias de enteros definidas de una forma mutuamente recursiva.

Los fractales pueden ser computados mediante funciones recursivas: esto, en algunos casos, puede resultar más ordenado usando funciones mutuamente recursivas; la curva de Sierpinski es un buen ejemplo.

Prevalencia

La recursión mutua es muy común en el ámbito de programación funcional y es regularmente usado en programas desarrollados in LISP, Scheme, ML y lenguajes similares. En lenguajes como Prolog, el uso de la recursión mutua es casi inevitable.

Algunos estilos de programación no incentivan el uso de la recursión mutua, aludiendo a que podría resultar confuso distinguir entre las condiciones en las cuales el programa retorna un resultado de las cuales generarían que el programa nunca termine su ejecución y no genere un resultado. Peter Norvig señala a un patrón de diseño que desalienta su uso por completo, indicando:

Si tienes dos funciones mutuamente recursivas que alteran el

estado de un objeto, intenta establecer todas las instrucciones en solo una de

las funciones. De otro modo probablemente termines duplicando tu código.

Terminología

La recursión mutua es también conocida como recursión indirecta, en contraste con la recursión directa donde una función se llama a sí misma directamente. Esto solo es una diferencia de énfasis, no diferentes nociones: la recursión indirecta se refiere a una sola función, mientras la recursión mutua se refiere a un conjunto de funciones y no a una función individual. Por ejemplo, si f se llama a sí misma, eso es la recursión directa. En cambio, si f llama a g y luego g llama a f, que vuelve a llamar a g, desde el punto de la función f, f es indirectamente recursiva, desde el punto de g, esta también es indirectamente recursiva, mientras que desde el punto de f y g, son mutuamente recursivas una en la otra. Análogamente en un conjunto de tres o más funciones que se llaman una a la otra pueden ser denominadas un conjunto de funciones mutuamente recursivas.

Conversión a recursión simple

Matemáticamente, un conjunto de funciones mutuamente recursivas son funciones recursivas primitivas, los cuales pueden ser probados por la recursion de cursos de valores, construyendo una sola función F que enlista los valores de la función individual recursiva en orden:

Cualquier recursión mutua entre dos procedimientos puede ser convertida en recursión simple adjuntando el código de un procedimiento al otro.^[2] Si hay solo un sitio donde un procedimiento llama el otro, esto es simple, aun así si hay muchos puede implicar duplicación de código. En términos de la pila de llamadas, dos procedimientos mutuamente recursivos generan una pila ABABAB..., y adjuntando B dentro de A genera una recursión simple (AB)(AB)(AB)...

Alternativamente, cualquier número de procedimientos se pueden fusionar en un único procedimiento que toma como argumento una variante de registro (o datos algebraicos) que representan la selección de un procedimiento y de sus argumentos; luego el procedimiento de la fusión envía en su argumento para ejecutar el código correspondiente y utiliza la recursión simple para llamar a sí mismo como corresponda. Esto puede ser visto como una aplicación limitada de desfuncionalización.^[3] Esta traducción puede ser útil cuando alguno de los procedimientos mutuamente recursivos pueden ser llamados por un código externo, así que no hay causa evidente para adjuntar un procedimiento dentro del otro. Luego dicho código debe modificarse para que los procedimientos de llamadas se realicen mediante la combinación de argumentos en una variante de registro como se describe; alternativamente, los procedimientos de envoltura podría ser utilizado para esta tarea.

Véase también

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', Proceedings of the 13th annual conference on Innovation and technology in computer science education, June 30–July 2, 2008, Madrid, Spain.
↑ On the Conversion of Indirect to Direct Recursion by Owen Kaser, C. R. Ramakrishnan, and Shaunak Pawagi at State University of New York, Stony Brook (1993)
↑ Reynolds, John (August 1972). «Definitional Interpreters for Higher-Order Programming Languages». Proceedings of the ACM Annual Conference. Boston, Massachusetts. pp. 717-740.

Harper, Robert (Harper, Robert (2000), Programming in Standard ML .), Programando en Estándar ML
Harvey, Brian; Wright, Matthew (1999). Sencillamente Esquema: Introduciendo Informática. MIT Prensa. Harvey, Brian; Wright, Matthew (1999). Simply Scheme: Introducing Computer Science. MIT Press. ISBN 978-0-26208281-5.
Hutton, Graham (2007). Programming in Haskell. Cambridge University Press. 2007. ISBN 978-0-52169269-4. Cambridge Prensa universitaria.