Recursión mutua

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

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.

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.

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.