Mutual recursion: Difference between revisions

Revision as of 15:10, 18 November 2017

Latest revision as of 04:28, 15 July 2025

(38 intermediate revisions by 26 users not shown)

Line 1:

{{short description|Two functions defined from each other}}

<!-- [[WP:NFCC]] violation: [[File:DrawingHands.jpg|thumb|upright|"[[Drawing Hands]]", a drawing by [[M. C. Escher]]]] -->In [[mathematics]] and [[computer science]], '''mutual recursion''' is a form of [[recursion]] where two mathematical or computational objects, such as functions or data types, are defined in terms of each other.<ref>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.</ref> Mutual recursion is very common in [[functional programming]] and in some problem domains, such as [[recursive descent parser]]s, where the data types are naturally mutually recursive.

<!-- [[WP:NFCC]] violation: [[File:DrawingHands.jpg|thumb|upright|"[[Drawing Hands]]", a drawing by [[M. C. Escher]]]] -->

<!-- [[WP:NFCC]] violation: [[File:DrawingHands.jpg|thumb|upright|"[[Drawing Hands]]", a drawing by [[M. C. Escher]]]] -->In [[mathematics]] and [[computer science]], '''mutual recursion''' is a form of [[Recursion (computer science)|recursion]] where two or more mathematical or computational objects, such as functions or data typesdatatypes, are defined in terms of each other.<ref>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.</ref> Mutual recursion is very common in [[functional programming]] and in some problem domains, such as [[recursive descent parser]]s, where the data typesdatatypes are naturally mutually recursive.

==Examples==

===Datatypes===

{{further|Recursive data type}}

===Tipos de datos:===

The most important basic example of a datatype that can be defined by mutual recursion is a [[tree (data structure)|tree]], which can be defined mutually recursively in terms of a forest (a list of trees). Symbolically:

f: <nowiki>[t[1], ..., t[k]]</nowiki>

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

Simbólicamente:

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

t: v f

A forest ''f'' consists of a list of trees, while a tree ''t'' consists of a pair of a value ''v'' and a forest ''f'' (its children). This definition is elegant and easy to work with abstractly (such as when proving theorems about properties of trees), as it expresses a tree in simple terms: a list of one type, and a pair of two types. Further, it matches many algorithms on trees, which consist of doing one thing with the value, and another thing with the children.

This mutually recursive definition can be converted to a singly recursive definition by [[Inline expansion|inlining]] the definition of a forest:

Un bosque f consiste en una lista de árboles, mientras 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.

t: v <nowiki>[t[1], ..., t[k]]</nowiki>

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

A tree ''t'' consists of a pair of a value ''v'' and a list of trees (its children). This definition is more compact, but somewhat messier: a tree consists of a pair of one type and a list of another, which require disentangling to prove results about.

In [[Standard ML]], the tree and forest datatypes can be mutually recursively defined as follows, allowing empty trees:{{sfn|Harper|2000|loc="[https://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm Date Types]"}}

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

<syntaxhighlight lang="sml">

datatype 'a tree = Empty | Node of 'a * 'a forest

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.

and 'a forest = Nil | Cons of 'a tree * 'a forest

En Standar ML, los tipos de datos de árbol y bosque se pueden definir mutual y recursivamente de la siguiente manera, lo que permite árboles vacíos:

</syntaxhighlight>

datatype 'a tree = Empty | Node of 'a * 'a forest

and 'a forest = Nil | Cons of 'a tree * 'a forest

===Computer functions===

Just as algorithms on recursive datatypes can naturally be given by recursive functions, algorithms on mutually recursive data structures can be naturally given by mutually recursive functions. Common examples include algorithms on trees, and [[recursive descent parser]]s. As with direct recursion, [[tail call optimization]] is necessary if the recursion depth is large or unbounded, such as using mutual recursion for multitasking. Note that tail call optimization in general (when the function called is not the same as the original function, as in tail-recursive calls) may be more difficult to implement than the special case of tail-recursive call optimization, and thus efficient implementation of mutual tail recursion may be absent from languages that only optimize tail-recursive calls. In languages such as [[Pascal (programming language)|Pascal]] that require declaration before use, mutually recursive functions require [[forward declaration]], as a forward reference cannot be avoided when defining them.

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.

As with directly recursive functions, a [[Recursion (computer science)#Wrapper function|wrapper function]] may be useful, with the mutually recursive functions defined as [[nested function]]s within its scope if this is supported. This is particularly useful for sharing state across a set of functions without having to pass parameters between them.

====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.

====Basic examples====

A standard example of mutual recursion, which is admittedly artificial, determines whether a non-negative number is even or odd by defining two separate functions that call each other, decrementing by 1 each time.{{sfn|Hutton|2007|loc=6.5 Mutual recursion, pp. [https://books.google.com/books?id=olp7lAtpRX0C&pg=PA53&dq=%22mutual+recursion%22 53–55]}} In C:

<syntaxhighlight lang=C>

bool is_even(unsigned int n) {

if (n == 0)

Line 43 ⟶ 42:

return is_even(n - 1);

}

</syntaxhighlight>

¿Esas funciones son basadas en la observación de la pregunta 4 es par? Lo cual es equivalente a ¿3 es impar? El cual a su vez equivale a preguntarnos si ¿2 es par?, y así sucesivamente hasta llegar a cero. Este ejemplo es una solo una mutual recursión, y podría ser 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. In C, esto tomaría O(n) de espacio de pilas, a menos que se reescriba la función usando saltos en vez de llamados. Esto podría se reducido por solo una función recursiva is_even. En ese caso, is_odd,el cual podría ser alineado, llamarí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-arboles(children), y puede ser dividido dentro de dos funciones mutuamente recursivas. Una especificando el comportamiento en un árbol, llamando a la función forest para el conjunto de sub-arboles, 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:

These functions are based on the observation that the question ''is 4 even?'' is equivalent to ''is 3 odd?'', which is in turn equivalent to ''is 2 even?'', and so on down to 0. This example is mutual [[single recursion]], and could easily be replaced by iteration. In this example, the mutually recursive calls are [[tail call]]s, and tail call optimization would be necessary to execute in constant stack space. In C, this would take ''O''(''n'') stack space, unless rewritten to use jumps instead of calls.<ref>"[http://www.cs.bu.edu/~hwxi/ATS/DOCUMENT/TUTORIALATS/HTML/c244.html Mutual Tail-Recursion]" and "[http://www.cs.bu.edu/~hwxi/ATS/TUTORIAL/contents/tail-recursive-functions.html Tail-Recursive Functions]", ''[http://www.cs.bu.edu/~hwxi/ATS/DOCUMENT/TUTORIALATS/HTML/book1.html A Tutorial on Programming Features in ATS],'' Hongwei Xi, 2010</ref> This could be reduced to a single recursive function <code>is_even</code>. In that case, <code>is_odd</code>, which could be inlined, would call <code>is_even</code>, but <code>is_even</code> would only call itself.

def f_tree(tree):

f_value(tree.value)

f_forest(tree.children)

As a more general class of examples, an algorithm on a tree can be decomposed into its behavior on a value and its behavior on children, and can be split up into two mutually recursive functions, one specifying the behavior on a tree, calling the forest function for the forest of children, and one specifying the behavior on a forest, calling the tree function for the tree in the forest. In Python:

def f_forest(forest):

<syntaxhighlight lang="python">

for tree in forest:

def f_tree(tree) -> None:

f_value(tree.value)

f_forest(tree.children)

def f_forest(forest) -> None:

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.

for tree in forest:

def f_tree(tree):

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:

</syntaxhighlight>

In this case the tree function calls the forest function by single recursion, but the forest function calls the tree function by [[multiple recursion]].

Using the Standard ML datatype above, the size of a tree (number of nodes) can be computed via the following mutually recursive functions:{{sfn|Harper|2000|loc="[https://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm Datatypes]"}}

<syntaxhighlight lang="sml">

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'

</syntaxhighlight>

A more detailed example in [[Scheme (programming language)|Scheme]], counting the leaves of a tree:{{sfn|Harvey|Wright|1999|loc=V. Abstraction: 18. Trees: Mutual Recursion, pp. [https://books.google.com/books?id=igJRhp0KGn8C&pg=PA310&dq=%22mutual%20recursion%22 310–313]}}

Un ejemplo mas detallado en Scheme, contando lo dejado de una árbol:

<syntaxhighlight lang=scheme>

(define (count-leaves tree)

(if (leaf? tree)

Line 75 ⟶ 78:

(+ (count-leaves (car forest))

(count-leaves-in-forest (cdr forest)))))

</syntaxhighlight>

These examples reduce easily to a single recursive function by inlining the forest function in the tree function, which is commonly done in practice: directly recursive functions that operate on trees sequentially process the value of the node and recurse on the children within one function, rather than dividing these into two separate functions.

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, el cual 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-arboles dentro de una función en lugar de dividirlas dentro de dos funciones separadas.

====EjemplosAdvanced avanzadosexamples====

A more complicated example is given by [[recursive descent parser]]s, which can be naturally implemented by having one function for each [[Production (computer science)|production rule]] of a grammar, which then mutually recurse; this will in general be multiple recursion, as production rules generally combine multiple parts. This can also be done without mutual recursion, for example by still having separate functions for each production rule, but having them called by a single controller function, or by putting all the grammar in a single function.

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, aun teniendo aun 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.

Mutual recursion can also implement a [[finite-state machine]], with one function for each state, and single recursion in changing state; this requires tail call optimization if the number of state changes is large or unbounded. This can be used as a simple form of [[cooperative multitasking]]. A similar approach to multitasking is to instead use [[coroutine]]s which call each other, where rather than terminating by calling another routine, one coroutine yields to another but does not terminate, and then resumes execution when it is yielded back to. This allows individual coroutines to hold state, without it needing to be passed by parameters or stored in shared variables.

Recursión mutua puede También implementar una maquina 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, el cual llama a cada otro, donde en lugar de llamar a otra rutina cede a otro, pero no lo termina, y luego pasara a la ejecución cuando es cedido de regreso. Eso permite cortinas individuales para mantener el estado, sin su necesidad de pasar por otros parámetros en variables compartidas.

Existen algunos algoritmos los cuales naturalmente tienes dos fases, como MIN MAX (min y máx.), y esos pueden ser implementados teniendo cada fase en una función separadas con recursión mutua, a pesar de que ellos pueden También ser combinados dentro de una sola función con recursión directa.

There are also some algorithms which naturally have two phases, such as [[minimax]] (min and max), which can be implemented by having each phase in a separate function with mutual recursion, though they can also be combined into a single function with direct recursion.

===Funciones matemáticas===

En matemáticas, las secuencias [[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 computarizados mediante funciones recursivas: Esto, en algunos casos, puede resultar más ordenado usando funciones mutuamente recursivas; la [[Sierpiński curve]] es un ejemplo.

===PrevalenciaMathematical functions===

In mathematics, the [[Hofstadter Female and Male sequences]] are an example of a pair of integer sequences defined in a mutually recursive manner.

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 Norving 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.

Fractals can be computed (up to a given resolution) by recursive functions. This can sometimes be done more elegantly via mutually recursive functions; the [[Sierpiński curve]] is a good example.

===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 mutualmente 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 mutualmente recursivas.

==Prevalence==

Mutual recursion is very common in the [[functional programming]] style, and is often used for programs written in [[Lisp (programming language)|LISP]], [[Scheme (programming language)|Scheme]], [[ML (programming language)|ML]], and similar [[programming language|languages]]s. For example, Abelson and Sussman describe how a [[meta-circular evaluator]] can be used to implement LISP with an eval-apply cycle.<ref>{{Cite book|last=Abelson|first=Harold|url=https://web.mit.edu/alexmv/6.037/sicp.pdf|title=Structure and Interpretation of Computer Programs|last2=Sussman|first2=Gerald Jay|last3=Sussman|first3=Julie|publisher=The MIT Press|year=1996|isbn=978-0262510875|___location=London, England|pages=492}}</ref> In languages such as [[Prolog programming language|Prolog]], mutual recursion is almost unavoidable.

Some programming styles discourage mutual recursion, claiming that it can be confusing to distinguish the conditions which will return an answer from the conditions that would allow the code to run forever without producing an answer. [[Peter Norvig]] points to a [[design pattern]] which discourages the use entirely, stating:<ref>[http://norvig.com/sudoku.html Solving Every Sudoku Puzzle]</ref>

{{quoteBlockquote|text=If you have two mutually-recursive functions that both alter the state of an object, try to move almost all the functionality into just one of the functions. Otherwise you will probably end up duplicating code.}}

==Terminology==

Mutual recursion is also known as [[indirect recursion]], by contrast with [[direct recursion]], where a single function calls itself directly. This is simply a difference of emphasis, not a different notion: "indirect recursion" emphasises an individual function, while "mutual recursion" emphasises the set of functions, and does not single out an individual function. For example, if ''f'' calls itself, that is direct recursion. If instead ''f'' calls ''g'' and then ''g'' calls ''f,'' which in turn calls ''g'' again, from the point of view of ''f'' alone, ''f'' is indirectly recursing, while from the point of view of ''g'' alone, ''g'' is indirectly recursing, while from the point of view of both, ''f'' and ''g'' are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.

== Conversion to direct recursion ==

Mathematically, a set of mutually recursive functions are [[primitive recursive]], which can be proven by [[course-of-values recursion]],<ref>"[http://planetmath.org/mutualrecursion mutual recursion]", ''PlanetMath''</ref> building a single function ''F'' that lists the values of the individual recursive function in order: <math>F = f_1(0), f_2(0), f_1(1), f_2(1), \dots,</math> and rewriting the mutual recursion as a primitive recursion.

Mathematically, a set of mutually recursive functions are [[primitive recursive]], which can be proven by [[course-of-values recursion]],<ref>"[http://planetmath.org/mutualrecursion mutual recursion]", ''PlanetMath''</ref> building a single function ''F'' that lists the values of the individual recursive function in order: <math>F = f_1(0), f_2(0), f_1(1), f_2(1), \dots,</math> and rewriting the mutual recursion as a primitive recursion.

Any mutual recursion between two procedures can be converted to direct recursion by inlining the code of one procedure into the other.<ref>[http://delivery.acm.org/10.1145/180000/176510/p151-kaser.pdf?key1=176510&key2=1857140721&coll=GUIDE&dl=GUIDE&CFID=82873082&CFTOKEN=54657523 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)</ref> If there is only one site where one procedure calls the other, this is straightforward, though if there are several it can involve code duplication. In terms of the call stack, two mutually recursive procedures yield a stack ABABAB..., and inlining B into A yields the direct recursion (AB)(AB)(AB)...

Alternately, any number of procedures can be merged into a single procedure that takes as argument a [[variant record]] (or [[algebraic data type]]) representing the selection of a procedure and its arguments; the merged procedure then dispatches on its argument to execute the corresponding code and uses direct recursion to call self as appropriate. This can be seen as a limited application of [[defunctionalization]].<ref>{{cite conference

| first = John | last = Reynolds | authorlinkauthor-link = John_C._Reynolds

| title = Definitional Interpreters for Higher-Order Programming Languages

| booktitlebook-title = Proceedings of the ACM Annual Conference

| date = August 1972

| ___location = Boston, Massachusetts

| pages = 717–740

| url = http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf

}}</ref> This translation may be useful when any of the mutually recursive procedures can be called by outside code, so there is no obvious case for inlining one procedure into the other. Such code then needs to be modified so that procedure calls are performed by bundling arguments into a variant record as described; alternately, wrapper procedures may be used for this task.

== See also ==

== See also ==

* [[Cycle detection (graph theory)]]

* [[Recursion (computer science)]]

* [[Circular dependency]]

== References ==

{{Reflist}}

* {{citation|first=Robert|last=Harper|authorlinkauthor-link=Robert Harper (computer scientist)|url=httphttps://www.cs.cmu.edu/~rwh/introsml/|title=Programming in Standard ML|year=2000}}

* {{cite book |title=Simply Scheme: Introducing Computer Science |last1=Harvey |first1=Brian |last2=Wright |first2=Matthew |year=1999 |publisher=MIT Press |isbn=978-0-26208281-5 |ref=harv }}

* {{cite book |title=Programming in Haskell |last=Hutton |first=Graham |year=2007 |publisher=Cambridge University Press |isbn=978-0-52169269-4 |ref=harv }}

== External links ==