Mutual recursion: Difference between revisions

Revision as of 20:29, 30 November 2019

Revision as of 14:53, 18 December 2019

Line 49:

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:

<source lang="python">

def f_tree(tree) -> None:

f_value(tree.value)

f_forest(tree.children)

def f_forest(forest) -> None:

for tree in forest:

f_tree(tree)

</source>

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