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 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: