Recursive Algorithm
A Recursive Algorithm is an algorithm (that applies a recursive function.
- Context:
- It can be applied by a Recursive Software Program (to solve a recursive task).
- Example(s):
- a Recursive Menu Printing Algorithm (e.g. implemented by a recursive Python program).
- …
- Counter-Example(s):
- See: Algorithm Strategy, Subproblem, Dynamic Programming.
References
2015a
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/recursion_(computer_science) Retrieved:2015-7-9.
- Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."
Most computer programming languages support recursion by allowing a function to call itself within the program text. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory provesthat these recursive-only languages are Turing complete; they are as computationally powerful as Turing complete imperative languages, meaning they can solve the same kinds of problems as imperative languages even without iterative control structures such as “while” and “for”.
- Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
2015b
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/recursion_(computer_science)#Recursion_versus_iteration Retrieved:2015-7-9.
- Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used. In imperative programming, iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in functional languages recursion is preferred, with tail recursion optimization leading to little overhead, and sometimes explicit iteration is not available.
Compare the templates to compute xn defined by xn = f(n, xn-1) from xbase:
- Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used. In imperative programming, iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in functional languages recursion is preferred, with tail recursion optimization leading to little overhead, and sometimes explicit iteration is not available.
function recursive(n)
if n==base
return xbase
else
return f(n, recursive(n-1))
|
function iterative(n)
x = xbase
for i = n downto base
x = f(i, x)
return x
|
- For imperative language the overhead is to define the function, for functional language the overhead is to define the accumulator variable x.
For example, the factorial function may be implemented iteratively in C by assigning to an loop index variable and accumulator variable, rather than passing arguments and returning values by recursion:
unsigned int factorial(unsigned int n) {
unsigned int product = 1; // empty product is 1
while (n) {
product *= n;
--n;
}
return product;
}
1996
- (Wall et al., 1996) ⇒ Larry Wall, Tom Christiansen, and Randal L. Schwartz. (1996). “Programming Perl, 2nd edition." O'Reilly. ISBN:1565921496
- QUOTE: recursion: The art of defining something (at least partly) in terms of itself by means of recursion, which is a naughty no-no in dictionaries.
1990
- (Graham et al., 1990) ⇒ Roland Graham, Donald Knuth, and Oren Patashnik. (1990). “Concrete Mathematics." http://www-cs-faculty.stanford.edu/~knuth/gkp.html Chapter 1: Recurrent Problems
1976
- (Wirth, 1976) ⇒ Niklaus Wirth. (1976). “Algorithms + Data Structures = Programs." Prentice-Hall