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 E. Black.
Entry modified 4 January 2005.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "recursion tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 4 January 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/recursionTree.html