Difference between revisions of "Recursion (computer science)"
Karl Jones (Talk | contribs) (Created page with "In computer science, '''recursion''' is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration)....") |
Karl Jones (Talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | In [[computer science]], '''recursion''' is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). | + | In [[computer science]], '''recursion''' 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 approach can be applied to many types of problems, and recursion is one of the central ideas of computer science. | ||
| Line 7: | Line 7: | ||
"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." | "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. | + | Most computer programming languages support recursion by allowing a [[Function (computer science)|function]] to call itself within the program text. Some [[Functional programming|functional programming languages]] do not define any looping constructs but rely solely on recursion to repeatedly call code. |
[[Computability theory]] proves that these recursive-only languages are [[Turing completeness|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”. | [[Computability theory]] proves that these recursive-only languages are [[Turing completeness|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”. | ||
== See also == | == See also == | ||
| + | |||
| + | * [[Functional programming]] | ||
| + | * [[Hierarchical and recursive queries in SQL]] | ||
| + | * [[Kleene–Rosser paradox]] | ||
| + | * [[Open recursion]] | ||
| + | * [[Recursion]] | ||
| + | * [[Sierpiński curve]] | ||
| + | |||
| + | === Recursive functions === | ||
| + | |||
| + | * [[μ-recursive functions]] | ||
| + | * [[McCarthy 91 function]] | ||
| + | * [[Primitive recursive functions]] | ||
| + | * [[Tak (function)]] | ||
== External links == | == External links == | ||
Revision as of 13:59, 15 September 2016
In computer science, recursion 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.
Description
"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 proves that 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”.
See also
- Functional programming
- Hierarchical and recursive queries in SQL
- Kleene–Rosser paradox
- Open recursion
- Recursion
- Sierpiński curve
Recursive functions
External links
- [] @ Wikipedia.org
[[Category:]] [[Category:]]
