Content deleted Content added
Paul August (talk | contribs) cat |
→Recursive algorithms: clarification that recursive functions and iteration are equivlently expressive |
||
Line 5:
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.
Any function that can be evaluated by a computer can be expressed in terms of recursive functions, without use of [[iteration]] through use of [[Continuation|continuations]], 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.
Line 20:
In addition, some numerical methods for finding approximate solutions to mathematical equations use recursion. In [[Newton's method]], for example, an approximate root of a function is provided as initial input to the method. The calculated result (output) is then used as input to the method, with the process repeated until a sufficiently accurate value is obtained.
==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 is analytic, and is the most common design for parsers for computer languages.
| |||