Mutual recursion: Difference between revisions

Revision as of 16:10, 7 June 2018

Revision as of 20:22, 29 August 2019

Line 15:

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 data types can be mutually recursively defined as follows, allowing empty trees:{{sfn|Harper|2000|loc="[httphttps://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm Date Types]"}}

<source lang=ocaml>

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

Line 59:

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]] data type above, the size of a tree (number of nodes) can be computed via the following mutually recursive functions:{{sfn|Harper|2000|loc="[httphttps://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm Datatypes]"}}

<source lang=ocaml>

fun size_tree Empty = 0

Line 127:

== References ==

{{Reflist}}

* {{citation|first=Robert|last=Harper|authorlink=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 }}