Recursion

As recursion (Latin recurrere run back ' ) refers to the technique in mathematics, logic and computer science, to define a function by itself ( recursive definition ). If you define multiple functions through mutual use of each other, it is called mutual recursion.

Not every recursive definition is a definition in the strict sense, because the definable function need not be well defined. Each call to the recursive function must be able to resolve by unfolding the recursive definition in finitely many steps. If this is not fulfilled, then one speaks of an infinite regress ( vulgo infinite loop ).

Recursion is a problem-solving strategy, it often leads to elegant presentations. The basic principle of recursion is the return of a general task to a simpler task of the same class. In many programming languages, recursive procedures and functions are available as language elements. Recursion and iteration are the same powerful language means substantially.

Definition

( Note in advance: recursion and recursive definitions are not limited to functions of natural numbers Here, we refer to the generalized recursion. . )

The basic principle of the recursive definition of a function f: The function value f ( n 1 ) of a function f: N0 → N0 is obtained by combining already calculated values ​​f ( n ), f ( n -1) ... If the function values of f are known for sufficiently many start arguments, each function value of f can be calculated. In a recursive definition of a function f, the function calls itself repeatedly, until altered by calling the function variable reaches a predetermined target value or limit value has been exceeded (termination, termination condition ).

The definition of recursively defined functions is a basic procedure in functional programming. Starting from some given functions (such as the sum function) new functions are defined. With these additional functions can be defined.

A particular case of recurrence is the primitive recursion that can be always replaced by an iteration. In such a recursion, the call tree contains no branches, that is, it is a call chain: this is always the case when a recursive function calls itself only once. The call can take place at the beginning ( Head Recursion, see Infiniter recourse) or end ( Tail Recursion or tail recursion ) function. Conversely, each iteration can be replaced by a primitive recursion, without thereby changing the complexity of the algorithm.

Forms of recursion

The most common Rekursionsform is the linear recursion, in which may be at most one recursive call in any case, the recursive definition. The calculation then proceeds along a chain of calls.

The recursion primitive is a special case of the linear recursion. Here we define functions on the natural numbers, in each recursive call the first parameter by one decreases or increases. Each primitive recursive definition can be (eg For Loop or While Loop ) replaced with the aid of a stack through a loop ( programming).

The terminal or repetitive recursion (tail recursion or recursion ) is the special case of linear recursion, where each recursive call is the last action of the recursive call. Endre Course ions can be directly replaced by while loops and vice versa.

Under nested recursion refers to a recursion in which recursive calls in parameter expressions occur recursive calls. This Rekursionsform is considered extremely difficult to understand.

Catkins recursion refers to the case where multiple recursive calls are next to each other. The recursive calls then form a tree. Catkins recursion is considered elegant, but can draw without further measures an exponential computation burden. It is like used as a starting point for the derivation of another efficient formulation.

The mutual recursion refers to the definition of several functions through mutual use of each other. It can be traced back to the ordinary recursion a tupelwertigen function.

Application

In the case of primitive recursive functions, it is up to the programmer to choose an iterative or a recursive implementation. The recursive implementation is most elegant, during the iterative implementation is more efficient (in particular, because the stack is subjected to less stress and the overhead for the repeated function call is missing); see also the programming example below.

Some programming languages ​​( for example, in functional programming) do not allow for iteration, so there is always the recursive implementation must be selected. Such languages ​​often set to optimize primitive recursion internally iterations to (some interpreter for Lisp and Scheme procedures above).

It should be noted that a naive implementation with some functions (e.g., Fibonacci numbers) implies that partial solutions can be calculated several times. A remedy for this example, the memoization that already calculated intermediate solutions is based on the reuse. The recursion is an essential part of some design strategies for efficient algorithms, particularly divide-and -conquer strategy ( Divide and Conquer ). Other approaches (eg, so-called greedy algorithms ) require an iterative procedure. Recursion and primitive recursive functions play an important role in theoretical computer science, especially in complexity theory and computability theory (see lambda calculus and Ackermann function).

In the recursive descent compiler ( Recursive Descent ) is a technique in which a language is parsed recursively.

Examples

The function is to calculate for each number is the sum of the natural numbers up to and including. It is defined as follows:

In order to obtain an equivalent recursive definition of the sum function, we first determine the simple case, the Recursion. In the example it is the function value.

What remains is the difficult case, in this case the function value. The difficult case we run back to a simpler case, namely the case. This simpler case is our recursive call. The relevant provision is called recursion. For example, can the sum of the natural numbers up to and including calculated by calculating the sum of the natural numbers up to and including and added to the number:

These two equations can be combined to form a recursive definition of the sum function:

It is a linear recursion, because in either case ( and recursion Recursion ) there is at most one sum call. There is even a primitive recursion. In the illustrated definition is not tail recursion, because after the recursive call must still be added.

The sum of the numbers up is then calculated as follows:

The call chain looks like this:

There is also a characterization of the sum function without recursion: the Gaussian sum formula states that.

Another classic example of a recursive function is the Fibonacci sequence

The Fibonacci function which assigns to each the - th Fibonacci number, has the simple cases and and satisfies the recurrence equation

This gives the recursive definition:

This recursive definition is cascaded. The third Fibonacci number is calculated as follows:

The calculation is performed for several times here. This indicates that there is potential for optimization. Also for the Fibonacci function, there is an equivalent closed expression.

Programming Example I, methodology recursive implementation

Iterative implementation

In the following example, a string of Offset 0 is n through implementativ iteratively to offset. The termination condition is satisfied if the iterator encounters the null terminator of the string.

Char * strKette = " foobar "       * PTemp = strKette;     while ( * pTemp! = 0x0 )   {     / / Output eg letter for letter     putchar (* pTemp );     pTemp;   }; recursive implementation

However, the iteration of a string can also implementativ represent recursively, even if the task does not implicitly is calculated recursively.

Void fnTraverse (char * pString )   {     if ( * pString == 0x0 )       return;     else       / / Output eg letter for Buchst.       putchar (* pString );       fnTraverse ( pString );   } Programming Example II, Faculty of calculation

The example shows a popular and simple implementation of the factorial computation using pseudo code. The recursive version is here compared with an iterative variant for clarity. Here, the number, the faculty to be calculated.

Fakultät_rekursiv (s) {    when n < = 1        then return 1        else return ( n * fakultät_rekursiv ( n -1)) } The recursion comes in the penultimate line to express where the function calls itself with a decreased by 1 point. In the next example, the function is called only once and then is linear the given algorithm from:

Fakultät_iterativ (s) {      faculty = 1      factor = 2      while factor <= n      {          faculty faculty * = factor          factor = factor 1      }      return faculty } Recursive graphics

Not only functions but also point sets can be defined recursively ( fractals ). Their graphical representation provides aesthetically pleasing, natural-looking structure. One example is the recursive Pythagoras Tree. The corresponding algorithm is as follows:

• Build two given points a square.
• On the top draw a triangle with defined angles or height.
• Call this function for the two legs of this triangle.

The algorithm is then unfolded to a predetermined recursion. In recursion one a triangle with one square on the three sides produced. This looks like the illustration on the Pythagorean theorem - hence the name. The higher the level of recursion, the more similar the structure of a tree.

Solving recursion

When solving a recursion you are looking for a the run-time overhead, on the other hand, the explicit form of the recursion.

The expense can be determined as asymptotic Θ - Ο or barrier means Mastertheorem or substitution method. And the rate with subsequent induction skilled provides a way to determine an upper bound on the period.

The explicit form (also called closed form ) of the recurrence equation can be found, for example, by the generating function. A second possibility is to derive by subtraction of successive function values ​​of the recurrence.