Recursive programming

In recursive programming , a procedure , function, or method in a computer program calls itself (i.e., contains a recursion ). The mutual call also represents a recursion.

A termination condition in this function is important for recursive programming , because otherwise the recursive program would theoretically call itself infinitely often.

Recursive programming can be used, among other things, in procedural and object-oriented programming languages . Although these languages expressly allow recursion in their language standard , self-calls and reciprocal calls are the exception here (due to the programming paradigms used ). Even though recursion is often used in practice to improve the programming style , most of them are Functions in these languages are purely iterative .

In some languages, such as B. in some functional programming languages or macro processors , the recursive programming method must be used because iterative language constructs are missing.

Examples

Faculty

An example of using recursive programming is to calculate the factorial of a number. The factorial is the product of all integers from 1 up to that number. So the factorial of 4 is . ${\ displaystyle 1 \ times 2 \ times 3 \ times 4 = 24}$

Most mathematicians define the faculty this way (a recursive definition):

The factorial of the number 0 is by definition 1.
The factorial of an integer that is greater than zero is the product of this number with the factorial of the next lower integer.

The definition works like this:

If you want to calculate the factorial of 4 , you first have to calculate the factorial of 3 and multiply the result by 4.

If you want to calculate the factorial of 3, you first have to calculate the factorial of 2 and multiply the result by 3.

If you want to calculate the factorial of 2, you first have to calculate the factorial of 1 and multiply the result by 2.

If you want to calculate the factorial of 1, you first have to calculate the factorial of 0 and multiply the result by 1.

By definition, the factorial of 0 is 1.

The factorial of 1 is therefore 1 * 1 = 1

So the factorial of 2 is 1 * 1 * 2 = 2

So the factorial of 3 is 1 * 1 * 2 * 3 = 6

So the factorial of 4 is 1 * 1 * 2 * 3 * 4 = 24

In a programming language like Pascal that allows recursive programming, you can enter the faculty as follows:

A function factorial is defined , which receives a number x as input value. This function multiplies x by the return value of factorial (x - 1) except for x = 0 , then the function returns the result 1. This is the termination condition:

Recursive implementation of the factorial function

function factorial(x: Integer): Integer;
begin
    if x = 0 then
        factorial := 1
    else
        factorial := x * factorial(x - 1);
end;

With the starting number x = 4 would computer count:

4 * (3 * (2 * (1 * factorial(0))))

the result is then the correct result, namely 24.

Binary search

The binary search in an array can be implemented recursively . If the middle element is smaller than the element searched for, the back half of the array is searched recursively. If it is larger than the element searched for, the front half of the array is searched recursively. If it is the same as the element searched for, the search is over.

The termination condition for the recursion is fulfilled if the middle element is the same as the element searched for, i.e. the search is successful, or if the end index is less than the start index, i.e. the search is unsuccessful.

The following function ( method ) for recursive binary search is in the C # programming language :

int RekursiveBinaereSuche(int[] werte, int gesuchterWert, int startIndex, int endIndex)
{
    if (endIndex < startIndex)
    {
        // Wenn Element nicht gefunden, dann null zurückgeben
        return null;
    }
    int mittlererIndex = (startIndex + endIndex) / 2;
    if (werte[mittlererIndex] == gesuchterWert)
    {
        // Wenn Element gefunden, dann Index zurückgeben
        return mittlererIndex;
    }
    else
    {
        if (werte[mittlererIndex] < gesuchterWert)
        {
            // Rekursiver Aufruf der Funktion für die hintere Hälfte
            return RekursiveBinaereSuche(werte, gesuchterWert, mittlererIndex + 1, endIndex);
        }
        else
        {
            // Rekursiver Aufruf der Funktion für die vordere Hälfte
            return RekursiveBinaereSuche(werte, gesuchterWert, startIndex, mittlererIndex - 1);
        }
    }
}

Efficiency

Recursive programs are not good in general performance . As a result of the repeated function calls (incarnations), the same method entry code is processed over and over again and the context is saved with each incarnation , which leads to additional program code and higher memory consumption. However, all recursive algorithms can also be implemented through iterative programming and vice versa.

Faculty

The faculty could also have been implemented like this:

function factorial(x: Integer): Integer;
    var i, number: Integer;
begin
    number := 1;

    for i := 1 to x do
        number := number * i;

    factorial := number;
end;

The rule here is that iterative implementation is often more efficient for simple problems . So should z. For example, the faculty function can also be implemented iteratively in practice for reasons of efficiency. In the case of complicated problems (e.g. tasks with trees ), on the other hand, it is often worthwhile to use a recursive solution, since an iterative formulation for such problems can quickly become very confusing - and inefficient - because in the worst case the stack itself is caused by the iterative algorithm what has to be managed is what the processor does directly.

Not all high-level programming languages allow recursive calls. One example is Fortran . Other programming languages , on the other hand, are basically recursive (such as Prolog ). Such recursive programming languages and also other languages such as B. Scheme set the recursion most efficient order.

implementation

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

Space for results
Argument x
Return address

First, fac (4) would be called in the main program and the following information would be placed on the stack :

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
Stack pointer	${\ displaystyle \ rightarrow}$	3	Return address in the main program

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

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
		3	Return address in the main program
		4th	Space for results
		5	3 (argument)
Stack pointer	${\ displaystyle \ rightarrow}$	6th	Return address in the faculty function

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

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
		3	Return address in the main program
		4th	Space for results
		5	3 (argument)
		6th	Return address in the faculty function
		7th	Space for results
		8th	2 (argument)
Stack pointer	${\ displaystyle \ rightarrow}$	9	Return address in the faculty function

The argument is again not equal to 0, i.e. 2 * fac (1) .

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
		3	Return address in the main program
		4th	Space for results
		5	3 (argument)
		6th	Return address in the faculty function
		7th	Space for results
		8th	2 (argument)
		9	Return address in the faculty function
		10	Space for results
		11	1 (argument)
Stack pointer	${\ displaystyle \ rightarrow}$	12	Return address in the faculty function

The argument is again not equal to 0, i.e. 1 * fac (0) .

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
		3	Return address in the main program
		4th	Space for results
		5	3 (argument)
		6th	Return address in the faculty function
		7th	Space for results
		8th	2 (argument)
		9	Return address in the faculty function
		10	Space for results
		11	1 (argument)
		12	Return address in the faculty function
		13	Space for results
		14th	0 (argument)
Stack pointer	${\ displaystyle \ rightarrow}$	15th	Return address in the faculty function

Now the argument is 0, so the result is 1. We get the return address and the argument from the stack and write the 1 in the space provided. The return jump leads back to the faculty function:

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
		3	Return address in the main program
		4th	Space for results
		5	3 (argument)
		6th	Return address in the faculty function
		7th	Space for results
		8th	2 (argument)
		9	Return address in the faculty function
		10	Space for results
		11	1 (argument)
		12	Return address in the faculty function
Stack pointer	${\ displaystyle \ rightarrow}$	13	1 (result)

Now you can multiply the result with the argument (1 * 1). The new result is again 1. The return address and the argument are fetched from the stack and the new result is written in the space provided. Return to the faculty function:

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
		3	Return address in the main program
		4th	Space for results
		5	3 (argument)
		6th	Return address in the faculty function
		7th	Space for results
		8th	2 (argument)
		9	Return address in the faculty function
Stack pointer	${\ displaystyle \ rightarrow}$	10	1 (result)

Again the result is multiplied by the argument (1 * 2). Back to the faculty function:

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
		3	Return address in the main program
		4th	Space for results
		5	3 (argument)
		6th	Return address in the faculty function
Stack pointer	${\ displaystyle \ rightarrow}$	7th	2 (result)

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

Start of stack	${\ displaystyle \ rightarrow}$	1	Space for results
		2	4 (argument)
		3	Return address in the main program
Stack pointer	${\ displaystyle \ rightarrow}$	4th	6 (result)

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

Stack start
stack pointer

{\ displaystyle \ rightarrow}

1

24 (result)

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

Web links

Recursive programming

contents

Examples

Faculty

Binary search

Efficiency

Faculty

implementation

See also

Web links