(algorithmic technique)
Definition: An algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task.
Specialization (... is a kind of me.)
tail recursion, collective recursion.
See also iteration, divide and conquer, divide and marriage before conquest, recursive, recurrence relation.
Note:
Every recursive solution involves two major parts or cases, the second part having three components.
Depending on the problem, any of these may be trivial or complex.
Here are some exercises to help you learn recursion. Although recursion may not be the best way to write some of these functions, it is good practice.
See dynamic algorithms for an example of one trade-off between speed and clarity for a recursive vs. an iterative implementation. See the notes for the towers of Hanoi puzzle for another recursive and iterative solution. Bro. David Carlson's tutorial and code (C++) with examples for factorial, Fibonacci, quicksort, and merge sort.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 28 February 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black and Patrick Rodgers, "recursion", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 28 February 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/recursion.html