En matemáticas e informática , la recursividad mutua es una forma de recursión en la que dos objetos matemáticos o computacionales, como funciones o tipos de datos, se definen en términos de cada uno. [1] La recursividad mutua es muy común en la programación funcional y en algunos dominios de problemas, como los analizadores sintácticos descendentes recursivos , donde los tipos de datos son mutuamente recursivos de forma natural.
El ejemplo básico más importante de un tipo de datos que se puede definir mediante recursividad mutua es un árbol , que se puede definir recursivamente mutuamente en términos de un bosque (una lista de árboles). Simbólicamente:
Un bosque f consta de una lista de árboles, mientras que un árbol t consta de un par de un valor v y un bosque f (sus hijos). Esta definición es elegante y fácil de trabajar de forma abstracta (como cuando se prueban teoremas sobre las propiedades de los árboles), ya que expresa un árbol en términos simples: una lista de un tipo y un par de dos tipos. Además, coincide con muchos algoritmos en árboles, que consisten en hacer una cosa con el valor y otra con los hijos.
Esta definición recursiva mutua se puede convertir en una definición recursiva simple al incluir la definición de bosque:
Un árbol t consta de 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 consta de un par de un tipo y una lista de otro, que requieren desenmarañarse para probar los resultados.
En el ML estándar , los tipos de datos de árboles y bosques se pueden definir recursivamente de la siguiente manera, lo que permite árboles vacíos: [2]