Content deleted Content added
No edit summary |
Undo revision 98657023 by 202.59.80.55 (talk) |
||
Line 1:
'''Recursion in computer programming''' defines a function in terms of itself. One example application of recursion is in [[recursive descent parser]]s for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs, or other data can be defined, parsed, or produced by a finite computer program.
==Recursive algorithms==
A common method of simplification is to divide a problem into subproblems of the same type. As a [[computer programming]] technique, this is called [[divide and conquer algorithm|divide and conquer]], and it is key to the design of many important algorithms, as well as being a fundamental part of [[dynamic programming]].
Virtually all [[programming language]]s in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer (for most languages on most stack-based architectures) or the language implementation keeps track of the various instances of the function (on many architectures, by using a [[call stack]], although other methods may be used). Conversely, every recursive function can be transformed into an iterative function by using a [[stack (data structure)|stack]].
Any function that can be evaluated by a computer can be expressed in terms of recursive functions without the use of [[iteration]], in [[continuation-passing style]]; and conversely any recursive function can be expressed in terms of iteration.
To make a very literal example out of this: If an unknown word is seen in a book, the reader can make a note of the current page number and put the note on a stack (which is empty so far). The reader can then look the new word up and, while reading on the subject, may find yet another unknown word. The page number of this word is also written down and put on top of the stack. At some point an article is read that does not require any explanation. The reader then returns to the previous page number and continues reading from there. This is repeated, sequentially removing the topmost note from the stack. Finally, the reader returns to the original book. This is a recursive approach.
Some languages designed for [[logic programming]] and [[functional programming]] provide recursion as the only means of repetition directly available to the programmer. Such languages generally make [[tail recursion]] as efficient as iteration, letting programmers express other repetition structures (such as [[Scheme (programming language)|Scheme]]'s <code>map</code> and <code>for</code>) in terms of recursion.
Recursion is deeply embedded in the [[theory of computation]], with the theoretical equivalence of [[mu-recursive function]]s and [[Turing machine]]s at the foundation of ideas about the universality of the modern computer.
==Recursive programming==
One basic form of recursive computer program is to define one or a few '''base cases''', and then define rules to break down other cases into the base case. This ''analytic'' method is a common design for parsers for computer languages; see [[Recursive descent parser]].
Another, similar form is generative, or ''synthetic'', recursion. In this scheme, the computer uses rules to assemble cases, and starts by selecting a base case. This scheme is often used when a computer must design something automatically, such as code, a machine part or some other data.
One common example (using the [[Pascal (programming language)|Pascal]] programming language, in this case) is the function used to calculate the [[factorial]] of an [[integer]]:
| |||