Recursion

from Wikipedia, the free encyclopedia
An example of recursion: feedback in VLC media player when displaying your own screen .

As recursion ( Latin recurrere 'running back ) refers to the abstract process that rules are applied to a product that they have created themselves anew. This creates potentially infinite loops. Rules or rule systems are called recursive if they have the property of allowing recursion in principle.

Recursion is a central term in mathematics and computer science and has a wide range of other uses; these extend to art, where the phenomenon has also been referred to as mise en abyme .

Recursion is also a problem solving strategy. Complex issues can often be captured very elegantly with recursively formulated rules. The basic principle is then to reduce a general task to a simpler task of the same class. For example, recursive programming is part of many programming languages. Procedures or functions can call themselves. Recursion and iteration are essentially equally powerful language resources.

In mathematics and computer science, recursion also appears more specifically in the form that a function itself is called again in its definition ( recursive definition ) . If you define several functions by mutual use of one another, one speaks of mutual recursion . Not every recursive definition is a definition in the actual sense, because the function to be defined does not need to be well-defined . Every call of the recursive function must be resolved in a finite number of steps by unfolding the recursive definition. If this is not fulfilled, one speaks of an infinite regress (in computer science also referred to as an endless loop ).

Uses and examples of recursion

Recursive graphics

"Sprouting" Pythagorean tree

Among other things, point sets can also be defined recursively (this results in the so-called fractals ). Their graphic representation provides aesthetically pleasing, natural -looking structures. One example is the Pythagoras tree . The associated algorithm looks like this; the third part contains the recursion:

  • Build a square over two given points .
  • Draw a triangle on the top with given angles and height.
  • Apply the two steps above again to each of the two legs of the newly created triangle.

The algorithm is then unfolded to a given recursion depth . At recursion depth of one, a triangle with a square on each of the three sides is created. It looks like the illustration for the Pythagorean Theorem - hence the name. The higher the recursion depth, the more the structure resembles a tree.

Recursion in grammar

The grammar of natural languages is used in linguistics and the like. a. described with the help of so-called phrase structure rules . In the opinion of most linguists, all human languages ​​have the property of being constructed recursively (in contrast to signal systems in the animal kingdom). This arises because in the decomposition of a grammatical unit which is labeled with a category, the same category can appear again. An example is the phenomenon of the subordinate clauses , which is described here with the following simplified production rule:

  1. S → NP VP (a sentence consists of a noun phrase (as subject) and a verb phrase )
  2. VP → V NP * (a verb phrase consists of a verb and zero to many noun phrases as objects of the verb)
  3. VP → VS (a verb phrase consists of a verb and a subordinate clause as the object of the verb)

This grammar allows you to choose whether to spell out "VP" with rule 2 or 3. In the event that steps 1 and then 3 are called, a recursion results: The symbol S appears as the product of rule 3, which in turn represents the start of rule 1.

Recursion in Mathematics

Faculty

The function factorial of a number n> 1 is defined as the product of the numbers 1 to n:

Examples

If this list is to be continued, the recursivity is almost automatic. For the calculation of 5! you will not start from the beginning, but can fall back on previous results, so

In general, the function can be defined recursively :

The Fibonacci sequence

A classic example of a recursive function is the Fibonacci sequence , in which each additional term in the sequence is the sum of the two preceding ones:

In contrast to the factorial function, there is no trivial closed representation here. The simplest description is the recursive definition:

This recursive definition is cascaded. Using this definition, the third Fibonacci number is calculated as follows:

The calculation for is carried out several times here. This indicates that there is potential for optimization.

Recursive definition of a function and subtypes of recursion

Mathematical definition

( Note in advance: recursion methods and recursive definitions are not restricted to functions of natural numbers. Please refer to the generalized recursion scheme. )

The basic principle of the recursive definition of a function f is: The function value f ( n +1) of a function f  : N 0N 0 results from the combination of already calculated values f ( n ), f ( n -1), ... If the function values of f are known for a sufficient number of starting arguments, each function value of f can be calculated. With a recursive definition of a function f , the function calls itself until a variable changed by calling the function has reached a specified target value or exceeded a limit value (termination, termination condition).

The definition of recursively defined functions is a fundamental procedure in functional programming . New functions are defined on the basis of some given functions (such as the sum function). With these further functions can be defined.

A special case of recursion is primitive recursion , which can always be replaced by an iteration . With such a recursion, the call tree does not contain any branches, that is, it is a call chain: this is always the case when a recursive function calls itself only once. The call can be made at the beginning ( head recursion , see Infinite Regress ) or at the end ( tail recursion or end recursion ) of the function. Conversely, each iteration can be replaced by a primitive recursion without changing the complexity of the algorithm.

Forms of recursion

The most common form of recursion is linear recursion , in which, in each case of the recursive definition, at most one recursive call may occur. The calculation then runs along a chain of calls.

The primitive recursion is a special case of linear recursion. Here you define functions on the natural numbers, with the first parameter increasing or decreasing by one in each recursive call. Each primitive-recursive definition can be replaced by a loop (programming) (e.g. for loop or while loop ) with the help of a stack .

The terminal or repetitive recursion ( tail recursion or end recursion ) describes the special case of linear recursion, in which each recursive call is the last action of the recursive call. End recursions can be replaced directly by while loops and vice versa.

Under nested recursion is defined as a recursion, which occur in recursive calls in parameter expressions recursive calls. This form of recursion is extremely difficult to understand.

Cascading recursion describes the case in which several recursive calls are next to each other. The recursive calls then form a tree. Cascading recursion is considered elegant, but without further measures it can result in exponential calculation effort. It is often used as a starting point for deriving another, more efficient formulation.

The mutual recursion referred to the definition of several functions by mutual use of each other. It can be traced back to the usual recursion of a tuple-valued function.

Other uses: recursion in programming

High-level programming languages that work with functions usually also allow recursion. Most solutions can be solved recursively or iteratively , see Recursive Programming and Iterative Programming .

The source code of recursive programming is often more elegant than the iterative implementation, since no auxiliary variables and loop counters have to be defined. In terms of processing, iterative processes are usually more efficient and require less storage space. The reason is that the repeated function calls are placed on the stack with all of the temporarily stored values . In particular, the recursion can also cause a buffer overflow (stack overflow). When programming real-time systems on microcontrollers , recursion is therefore often avoided.

Some programming languages (for example in functional programming ) do not allow iteration, so the recursive implementation must always be selected. Such languages ​​often use primitive recursions for optimization, which are implemented internally as iterations (some interpreters for LISP and Scheme do the same).

It should be noted that a naive implementation of some functions (e.g. the Fibonacci numbers ) requires that partial solutions are calculated several times. In this example, the remedy is provided by memoization , which is based on the reuse of intermediate solutions that have already been calculated. Recursion is an essential part of some design strategies for efficient algorithms , especially the divide-and-conquer strategy (Divide and Conquer) . Other approaches (for example so-called greedy algorithms ) require an iterative approach. Recursion and primitive-recursive functions play a major role in theoretical computer science , especially in complexity theory and computability theory (see also lambda calculus and Ackermann function ).

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

Programming examples

The following example shows a simple and popular implementation of the factorial function in the Python programming language . The recursive variant is contrasted with an iterative variant for clarity. The recursion is expressed in that the function calls itself with an argument reduced by 1. Both implementations execute the algorithm with linear runtime complexity depending on the input parameter. While the space complexity remains constant in the iterative variant, the memory requirement increases linearly in the recursive variant, since a new memory area must be reserved for the local variables and the return address with each recursive function call. In functional programming, dynamic memory management is implemented using a call stack .

Iterative programming Recursive programming
def factorial(number):
    result = 1
    
    while number > 1:
        result *= number
        number -= 1
    
    return result
def factorial(number):
    if number <= 1:
        return 1
    
    return number * factorial(number - 1)

The next example implements the Fibonacci sequence in the C programming language . The recursive variant is a multiple recursion, which leads to exponential runtime and space complexity. The recursive function calls branch out to a binary tree in which identical partial results are calculated several times. Most often the Fibonacci numbers are calculated in the first two places, which define the termination condition in the recursion. In the iterative variant, the runtime complexity is linear and the space complexity is constant.

Iterative programming Recursive programming
int fibonacci(int number) {
    int first = 0, second = 1;

    for (int count = 0; count < number; ++count) {
        int swap = first;
        first = second;
        second += swap;
    }

    return first;
}
int fibonacci(int number) {
    if (number <= 0)
        return 0;

    if (number == 1)
        return 1;

    return fibonacci(number - 1) + fibonacci(number - 2);
}

Resolving recursions

When solving a recursion, one looks for the runtime effort on the one hand, and the explicit form of the recursion on the other.

The effort can be determined as an asymptotic Θ- or Ο-bound using the master theorem or substitution method. Even the clever rates with subsequent induction provides a way an upper bound to determine the duration.

The explicit form (or also called closed form) of the recursion equation can be found, for example, by the generating function. A second possibility is the derivation of successive function values ​​of the recurrence by forming the difference.

Use of the concept of recursion in other sciences

The concept of recursion is used in different ways in different disciplines. Five types of usage can be distinguished: The “organizational-syntactic” recursion in cognitive psychology, the “operational- functional ”recursion in technology theory and“ process emulative ”recursion in cultural evolution and civilization theory.

Cognitive psychology

The evolutionary cognitive psychologist Michael Corballis worked out an “organizational-syntactic” concept of recursion in his book The Recursive Mind . It shows that the human ability to nested levels of meaning and action in any depth and to open syntactic stringing together of operational units, as they basically occur in tool behavior and cooperation, precedes language ability and is a general characteristic of human cognition and action organization. Thus, the strong human ability to mental time travel and the theory of mind are based on the ability to recursion.

Engineering theory

The system theorist W. Brian Arthur developed an “operational-functional” concept of recursion in his book The Nature of Technology . Arthur shows that all technologies have a hierarchical nesting of elements and functional levels, with the lower elements receiving their operational functionality through recursion to the upper levels, as illustrated by the example of an aircraft carrier association: The turbine of a fighter jet consists of individual parts or "executables" such as Screws and air blades that are recursively embedded in the overall function of the turbine, just like the turbine is a recursively nested "executable" of the fighter jet, the fighter jet is an "executable" of the aircraft carrier association and this is an "executable" of a squadron.

Cultural evolution research and civilization theory

The entire technological and cultural development in the cultural evolution and history of civilization has the pattern of "prozessemulativen" recursion, as the sociologist Prior Löffler has demonstrated. "Process emulative" recursion describes a development mechanism in which an instrumental or intellectual process is abstracted and reintroduced as a material or media emulation. This can be demonstrated in the early technological evolution, in which stages of development can each be described as degrees of recursion. According to the current state of knowledge, summarized in the “model of the expansion of cultural capacities”, simple stone tools (“modular culture”,> 2.6 Ma ) follow from a developmental point of view composite tools such as hammer stones with handles or spears with bone points (“composite culture ”,> 500 ka ) Complementary, independent modules composed of devices such as a bow and arrow or needle and thread ("complementary culture",> 70 ka ), then ideal tools such as cave paintings, musical instruments or traps ("ideal culture",> 40 ka ). The technology structures of the cumulative development stages are based on the "process-emulative" recursion of the processes of the previous stages. For example, the apparatus of the bow and arrow ("complementary culture") recursively emulates the process of throwing a javelin ("composite culture") and the trap ("ideal culture") recursively emulates the presence of a group of hunters or the trap mechanism recursively emulates the triggering mechanism of the bow (" Complementary culture "). As a general principle, “process emulative” recursion runs through the entire history of technology: For example, the microwave oven is based on “process emulative” recursion, since it emulates the process of heating food, for example by an oven; The digital pattern recognition is based on the process-emulative recursion of human pattern recognition etc. It was shown that the development principle of the "process-emulative" recursion is also the basis of the developments of the entire history of civilization and occurs in addition to technology in other areas, such as economics, the media, the Politics, the development of cognitive structures, art and mathematics, with each stage of development in these areas being based on the recursive emulation of the processes of the previous stage of development. In this way, cumulative successive development phases in the history of civilization ( early advanced civilizations , Axial and modern times ) can be explained as an expression of “process-emulative” recursions.

See also

Web links

Wiktionary: recursion  - explanations of meanings, word origins, synonyms, translations
Wiktionary: recursive  - explanations of meanings, word origins, synonyms, translations

References and comments

  1. See e.g. B. Andrew Carnie: Constituent Structure. Second edition. Oxford University Press, 2010. On the subject of recursivity v. a. P. 84ff.
  2. Only for the language Pirahã has the thesis been put forward that it would know no recursion in the grammar, since there are no subordinate clauses. This analysis is controversial, see the linked article for details.
  3. For these five types see Davor Löffler: Generative Realities I. Technological civilization as a new Axial Age and level of civilization. An anthropology of the 21st century . Weilerswist: Velbrück Wissenschaft, 2019, pp. 195–204.
  4. Cf. Davor Löffler: Generative Realities I. Technological civilization as a new axial age and level of civilization. An anthropology of the 21st century . Weilerswist: Velbrück Wissenschaft, 2019, p. 197 f.
  5. Michael C. Corballis, The Recursive Mind. The Origins of Human Language, Thought, and Civilization . Princeton, NJ / Oxford: Princeton University Press, 2013.
  6. See Michael C. Corballis: The Recursive Mind. The Origins of Human Language, Thought, and Civilization . Princeton, NJ / Oxford: Princeton University Press, 2013, pp. 82–165.
  7. Cf. Davor Löffler: Generative Realities I. Technological civilization as a new axial age and level of civilization. An anthropology of the 21st century . Weilerswist: Velbrück Wissenschaft, 2019, p. 198 f.
  8. ^ W. Brian Arthur: The Nature of Technology. What It Is and How It Evolves . London: Penguin Books, 2009.
  9. See W. Brian Arthur: The Nature of Technology. What It Is and How It Evolves . London: Penguin Books, 2009, p. 29
  10. See W. Brian Arthur: The Nature of Technology. What It Is and How It Evolves . London: Penguin Books, 2009, pp. 39-44
  11. Cf. Davor Löffler: Generative Realities I. Technological civilization as a new axial age and level of civilization. An anthropology of the 21st century . Weilerswist: Velbrück Wissenschaft, 2019, pp. 199–204.
  12. Miriam N. Haidle, Michael Bolus, Mark Collard, et al .: The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals . In: Journal of Anthropological Sciences , Vol. 93, 2015, pp. 43–70.
  13. See Miriam N. Haidle, Michael Bolus, Mark Collard, et al .: The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals . In: Journal of Anthropological Sciences , vol. 93, 2015, p. 56 f.
  14. See Miriam N. Haidle, Michael Bolus, Mark Collard, et al .: The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals . In: Journal of Anthropological Sciences , vol. 93, 2015, p. 57 f.
  15. Miriam N. Haidle, Michael Bolus, Mark Collard, et al .: The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals . In: Journal of Anthropological Sciences , Vol. 93, 2015, p. 58.
  16. Miriam N. Haidle, Michael Bolus, Mark Collard, et al .: The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals . In: Journal of Anthropological Sciences , Vol. 93, 2015, pp. 58–60.
  17. A summarizing table can be found in Davor Löffler: Generative Realities I. Technological civilization as a new axial age and level of civilization. An anthropology of the 21st century . Weilerswist: Velbrück Wissenschaft, 2019, p. 600 f.
  18. Cf. Davor Löffler: Generative Realities I. Technological civilization as a new axial age and level of civilization. An anthropology of the 21st century . Weilerswist: Velbrück Wissenschaft, 2019, pp. 621–640.