(definition)
Definition: A method to analyze the complexity of an algorithm by diagramming the recursive function calls.
Formal Definition: A recursion tree T(p) of degree p is either (i) null or (ii) has p children which are recursion trees.
Note: Also known as an "R-tree".
Author: PEB
After [GCG92] and [CLR90, page 59]. Suggested by Rama Maiti, 19 August 2001.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 4 January 2005.
HTML page formatted Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "recursion tree", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 4 January 2005. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/recursionTree.html