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.​ 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 mutuamente recursivo 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 facilita trabajar abstractamente (como cuando se prueban teoremas sobre las propiedades de los árboles), dado que expresa a 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 incrustar 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 más desordenada: un árbol consiste en un par de un tipo y una lista de otro, que requiere ser expandidas para probar resultados.

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 sobre tipos de datos recursivos son dados por funciones recursivas, los algoritmos en las estructuras de datos mutuamente recursivas pueden ser dados por funciones mutuamente recursivas. Al igual que con la recursión directa, optimizar la recursión de cola es necesario si la recursión es demasiado profunda.

Al igual que con las funciones recursivas unarias, una función contenedora puede ser útil, con las funciones mutuamente recursivas definidas como funciones anidadas dentro suyo. Esto es particularmente útil ventajoso a la hora de compartir un estado común a todas ellas.

Ejemplos básicos

Un ejemplo estándar de recursión mutua es determinar si un número natural es par o impar por definición dos funciones que se llaman una a la otra, restando de a uno. 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);
}

El fundamento de esta implementación es la igualdad entre las preguntas "¿es 4 par?" a "¿es 3 impar?" Lo que a su vez equivale a preguntase "¿es 2 par?", y así sucesivamente hasta llegar a cero.

Pra un ejemplo más general, un algoritmo de un árbol puede ser descompuesto dentro de su comportamiento en un valor y el comportamiento de sus sub-árboles (children), que puede ser dividido dentro de dos funciones de recursión mutua. 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 recursión simple, 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 calculado con 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 Scheme, que cuenta 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 única función recursiva mediante la incrustación de la función forest en la función tree, una práctica comun: las funciones recursivas sobre árboles procesan secuencialmente el valor del nodo y recursan en los sub-árboles todo en una función, en lugar de estar divididas en dos funciones separadas.

Funciones matemáticas

En matemáticas, las sucesiones femenina y masculina de Hofstadter son un par de secuencias de enteros con una definición mutuamente recursiva.

Los fractales pueden ser computados mediante funciones recursivas, esto 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 desaconsejan el uso de la recursión mutua, aludiendo a que podría resultar confuso distinguir los parámetros que producen una respuesta de aquellos que no lo hacen. Peter Norvig señala un patrón de diseño que desalienta rotundamente su uso, indicando:^{[cita requerida]}

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.

Conversión a recursión simple

Matemáticamente, las funciones mutuamente recursivas son funciones recursivas primitivas, que puede ser demostrado por Recursión Global,​ construyendo una sola función F que enlista los valores de la función individual recursiva en orden: $F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,$ y reescribiendo la recursión mutua como recursión primitiva.

Cualquier recursión mutua entre dos procedimientos puede ser convertida en recursión simple incrustando el código de un procedimiento al otro.​ Si hay solo un sitio donde un procedimiento llama al otro esto es simple, pero de haber más de uno implica duplicar el código. En términos de la pila de llamadas, dos procedimientos mutuamente recursivos 'A', 'B' generan una pila 'ABABAB...', adjuntar a '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 representa la selección de un procedimiento y de sus argumentos; luego el procedimiento de la fusión ejecuta el código correspondiente y utiliza la recursión simple para llamar a sí mismo como corresponda.

Véase también

• Recursión

Referencias

• Harper, Robert (Harper, Robert (2000), Programming in Standard ML .)
• 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. 

Enlaces externos

• Recursión mutua en Rosetta Code

• Datos: Q3454656