0.4 Recursion

4. recursion

(From Wikipedia, the free encyclopedia)

Recursion in computer programming defines a function in terms of itself. One example application of recursion is in recursive descent parsers 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.

4.1. recursive algorithms

(From Wikipedia, the free encyclopedia)

A common method of simplification is to divide a problem into sub-problems of the same type. As a computer programming technique, this is called 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 languages 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 much architecture, 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 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 's map and for) in terms of recursion.

Recursion is deeply embedded in the theory of computation , with the theoretical equivalence of mu-recursive functions and Turing machines at the foundation of ideas about the universality of the modern computer.

4.2. recursive programming

(From Wikipedia, the free encyclopedia)

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.