Recursive Algorithm: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
A [[Recursive Algorithm]] is an [[ | A [[Recursive Algorithm]] is an [[algorithm]] that implements a [[recursive function]]. | ||
* <B><U>See</U>:</B> [[ | * <B><U>See</U>:</B> [[Iterative Algorithm]], [[Algorithm Strategy]], [[Subproblem]], [[Dynamic Programming]]. | ||
---- | |||
---- | |||
==References == | |||
===2009=== | |||
* [http://en.wikipedia.org/wiki/Recursion_(computer_science) http://en.wikipedia.org/wiki/Recursion_(computer_science)] | |||
** '''Recursion''' in [[Computing Science Subject Area|computer science]] is a way of thinking about and solving many types of problems. In fact, recursion is one of the central ideas of computer science (Epp, 1995). Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem (Graph & al, 1990). <P> "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." (Wirth, 1976). <P> Most high-level computer programming languages support recursion by allowing a function to call itself within the program text. [[Imperative Language|Imperative languages]] define looping constructs like “while” and “for” loops that are used to perform repetitive actions. Some [[Functional Language|functional programming languages]] do not define any looping constructs but rely solely on recursion to repeatedly call code. [[Computability Theory (Computer Science)|Computability theory]] has proven that these recursive only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like “while” and “for”. | |||
===1996=== | |||
* ([[1996_ProgrammingPerl|Wall & al, 1996]]) ⇒ [[Larry Wall]], Tom Christiansen, and Randal L. Schwartz. (1996). "[http://docstore.mik.ua/orelly/perl/prog Programming Perl, 2nd edition]." O'Reilly. ISBN:1565921496 | |||
** '''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. | |||
===1995=== | |||
* Susanna Epp. (1995). "Discrete Mathematics with Applications (2nd edition).'' | |||
===1990=== | |||
* Roland Graham, Donald Knuth, and Oren Patashnik. (1990). "Concrete Mathematics.</i>" http://www-cs-faculty.stanford.edu/~knuth/gkp.html Chapter 1: Recurrent Problems | |||
===1976=== | |||
* Niklaus Wirth. (1976). "Algorithms + Data Structures = Programs.</i>" Prentice-Hall | |||
---- | ---- | ||
__NOTOC__ | __NOTOC__ | ||
Revision as of 13:37, 10 July 2014
A Recursive Algorithm is an algorithm that implements a recursive function.
References
2009
- http://en.wikipedia.org/wiki/Recursion_(computer_science)
- Recursion in computer science is a way of thinking about and solving many types of problems. In fact, recursion is one of the central ideas of computer science (Epp, 1995). Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem (Graph & al, 1990).
"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." (Wirth, 1976).
Most high-level computer programming languages support recursion by allowing a function to call itself within the program text. Imperative languages define looping constructs like “while” and “for” loops that are used to perform repetitive actions. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory has proven that these recursive only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like “while” and “for”.
- Recursion in computer science is a way of thinking about and solving many types of problems. In fact, recursion is one of the central ideas of computer science (Epp, 1995). Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem (Graph & al, 1990).
1996
- (Wall & al, 1996) ⇒ Larry Wall, Tom Christiansen, and Randal L. Schwartz. (1996). "Programming Perl, 2nd edition." O'Reilly. ISBN:1565921496
- 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.
1995
- Susanna Epp. (1995). "Discrete Mathematics with Applications (2nd edition).
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
- Niklaus Wirth. (1976). "Algorithms + Data Structures = Programs." Prentice-Hall