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".
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 Fri Feb 23 10:06:08 2018.
Cite this as:
Paul E. Black, "recursion tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 4 January 2005. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/recursionTree.html