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 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: 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.
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: El fundamento de esta implementación es la igualdad entre las preguntas "¿es 4 par?"
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.
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.