Content deleted Content added
→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]] in [[Continuation-passing style|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.
| |||