recursion tree


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

More information

After [GCG92] and [CLR90, page 59]. Suggested by Rama Maiti, 19 August 2001.

Go to the Dictionary of Algorithms and Data Structures home page.

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:

to NIST home page