Recursion (computer science)

In recursive programming, a procedure, function or method calls back into a computer program itself. Also the mutual call represents a recursion

Important in the recursive programming is a termination condition in this function, because the recursive program (in theory) would infinitely often call themselves otherwise.

Recursive programming can be applied, inter alia, procedural and object -oriented programming languages ​​. Although these languages ​​express themselves in their language standard recursion, however, provide self- views and cross-calls here (due to the used programming paradigms ) the exception rather dar. Although in practice to improve the programming style ( readability / simpler implementation ) also here quite often on recursion recourse, most functions are in these languages ​​but purely iterative.

In some languages ​​, such as in some functional programming or macro processors, the recursive programming method have to use it, since iterative language constructs lacking.

Example

An example of the use of a recursive programming is to calculate the factorial of a number. The factorial is the product of all integers from 1 to that number. The Faculty of 4 is so.

Mathematicians define the faculty mostly as ( a recursive definition ):

  • The factorial of the number 0 is defined to be 1
  • The factorial of an integer that is greater than zero, the product of this number with the faculty of the next lowest whole number.

The definition works like this:

  • If you want to calculate the factorial of 4, one must first calculate and multiply the result by 4 factorial of 3.
  • If you want to calculate the factorial of 3, one must first calculate and multiply the result by 3 factorial of 2.
  • If you want to calculate the factorial of 2, one must first calculate and multiply the result by 2 factorial of 1.
  • If you want to calculate the factorial of 1, one must first calculate and multiply the result by 1, the factorial of 0.
  • The Faculty of 0 is by definition 1
  • The Faculty of so 1 is 1 * 1 = 1
  • The Faculty of 2 is thus 1 * 1 * 2 = 2
  • The faculty of 3 is therefore 1 * 1 * 2 * 3 = 6
  • The Faculty of 4 is thus 1 * 1 * 2 * 3 * 4 = 24

In a language such as Pascal, which permits recursive programming, you can enter the faculty as follows:

Defining a function of fac, gets a number x as input. This function multiplies x with the return value of fac ( x -1) except x = 0, then the function returns the result 1 This is the termination condition:

Recursive implementation of the factorial function

Function fac ( x: Integer): Integer; begin    if x = 0 then fac: = 1             else fac: = x * fac ( x - 1); end; With the starting number x = 4, the computer would calculate:

4 * (3 * (2 * (1 * FAC (0 )))) then out comes the correct result, namely 24

Efficiency

Recursive programs do not have good performance in general. Due to the repeated function calls ( incarnations ) the same methods entry code is edited and saved in every incarnation of context repeatedly, resulting in additional program code and higher memory consumption. All recursive algorithms, however, can also implement by iterative programming ( and vice versa). One would have the faculty also can implement this:

Iterative implementation of the factorial function

Function fac ( x: Integer): Integer;    var i, result: Integer; begin    Result: = 1;    for i: = 1 to x do result: = result * i;    fac: = result; end; In this case, the rule is that for simple problems an iterative implementation is often more efficient. For example, the factorial function for efficiency should be implemented iteratively in practice. For complicated problems ( eg tasks with trees ), however, is often worthwhile to use a recursive solution, since for such problems an iterative formulation quickly become very confusing - can be, because even in the worst case the stack by the iterative algorithm - and inefficient needs to be managed, what else does the processor directly.

Not all high-level languages ​​allow recursive calls; an example is Fortran. Other programming languages ​​are, in principle recursively (such as Prolog ). Such recursive programming languages ​​( and other languages ​​such as Scheme) set the recursion to most efficiently.

Implementation

Recursion is typically implemented by a stack that holds the return addresses, but also all local variables and possibly function results. If, as the factorial of 4 in the above example, each call would put the following information on the stack:

First, would the main program so fac ( 4 ) is called, thereby establishing the following information on the stack:

The factorial function now checks if the argument is 0. Since this is not the case, then 4 * FAC (3 ) is calculated. So first fac must be called with the argument 3:

The argument is again equal to 0, so continue with 3 * fac ( 2).

The argument is again equal to 0, also2 * fac ( 1).

The argument is again equal to 0, also1 * fac ( 0).

Now the argument is 0, the result is 1 thus we get the return address and the argument from the stack and write the 1 in the intended place. The return into the factorial function returns:

Now you can multiply the result with the argument (1 * 1). The new result is 1 The return address again and the argument will be popped from the stack and writes the new result in the space provided. Return to the factorial function:

In turn, the result is multiplied with the argument (1 * 2). Back in the factorial function:

The result is multiplied by the argument (2 * 3). Back in the factorial function:

The result is multiplied by the argument (6 * 4). Back to main program

The main program then has to pick from the stack only the result 24.

677428
de