recursion
(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. - base case(s), in which the problem is simple enough to be solved directly, and
- recursive case(s). A recursive case has three components:
- divide the problem into one or more simpler or smaller parts of the problem,
- call the function (recursively) on each part, and
- combine the solutions of the parts into a solution for the problem.
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. There are more exercises at Erwin's Programming with Recursion tutorial.
- Write a function to compute the sum of all numbers from 1 to n.
- Write a function to compute 2 to the power of a non-negative integer.
- Write a function to compute any number to the power of a non-negative integer.
- Write a function to compute the nth Fibonacci number.
- Write a function to compute the greatest common divisor (GCD) of two positive integers with Euclid's algorithm.
- Write a function to compute GCD based on the following relations
- GCD(2m, 2n) = 2 * GCD(m, n)
- GCD(2m, 2n+1) = GCD(m, 2n+1)
- GCD(2m+1, 2n+1) = GCD(n-m, 2m+1) if m < n
- GCD(m, m) = m
(after "ML for the Working Programmer", page 49). - Write a function to compute any number to the power of a non-negative integer using repeated squaring, that is, x2n = (xn)² and x2n+1 = x × x2n. (after "ML for the Working Programmer", pages 45 and 46).
- Write a function to compute the integer square root of a non-negative integer using square_root(4x) = 2*square_root(x). (after "ML for the Working Programmer", pages 48 and 49).
Authors: PEB,PR
More information
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. Erwin's Programming with Recursion tutorial.
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 Thu Oct 27 10:02:00 2005.
HTML page formatted Fri Dec 30 11:16:43 2005.
Cite this as:
Paul E. Black and Patrick Rodgers, "recursion", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/recursion.html
