What is recursion in a computer?

In mathematics and computer science, when a class or method can be defined by two attributes, they show recursive behavior:

Simple baseline condition-no recursive termination.

A set of rules reduces all other situations to baseline conditions.

For example, the following is a recursive definition of someone's ancestors:

Someone's parents are his ancestors (baseline condition)

One's ancestor's ancestor is also his ancestor (recursive step)

Fibonacci sequence is a classic example of recursion:

Fib(0) = 1 baseline condition1;

Fib( 1) = 1 baseline condition 2;

For all integers n, n >；; at 1:Fib(n)=(Fib(n- 1)+Fib(n-2))。

Many mathematical axioms are based on recursive rules. For example, the formal definition of natural numbers in Piano's axiom can be described as: 0 is a natural number, and every natural number has successors, which is also a natural number. Through this baseline condition and recursive rule, a set of all natural numbers can be generated.

Recursively defined mathematical objects include functions, sets, especially fractals.

Recursion also has many joking "definitions".

Informal definition

Recursion is a step of a program, which involves calling the program itself. The process of going through recursion is called recursion.

To understand recursion, we must recognize the difference between program and program running. A program is a set of steps based on a set of rules. The running of a program actually includes following rules and executing steps. For example, a program is like a handwritten recipe; Running a program is actually like preparing a meal.

Recursion is related to references to other programs in the process specification, but it is not the same. For example, a recipe may refer to cooking vegetables, and adding water in turn is another procedure. However, the recursive process means that (at least) one step needs a new instance of the same process, just as the sour dough recipe needs some dough left over from the last time the same recipe was made. This immediately creates the possibility of an infinite loop; If you skip the problematic steps in order to complete the program in some cases, recursion can only be used correctly in the definition, such as a sour dough recipe, which also tells you how to get some dough if you have never made dough before. Even if the definition is correct, the recursive process is not easy for human beings to execute, because it is necessary to distinguish between new calls and old calls (partial execution); This requires some management of the progress of various synchronous instances of the program. Therefore, recursive definitions are very rare in everyday situations. An example can be the following process of finding a maze road, going straight until you reach the exit or the branch point (a dead corner is considered as the branch point of the 0 branch). If the point reached is the exit, terminate. Otherwise, recursively use this procedure to try each branch in turn; If each experiment only reaches a dead end and fails, then go back to the path leading to this branch point and report the failure. Whether this really defines the termination process depends on the nature of the maze: it does not allow loops. In any case, to carry out this process, you must carefully record all the branches currently explored and which branches have been thoroughly tried.

In language

Many people, such as linguist Noam Chomsky, believe that there is no upper limit on the number and length of grammatical sentences in a language (beyond the actual limit, such as speaking time), which can be explained as the result of recursion in natural language. This can be understood by the recursive definition of syntactic categories. For example, a sentence can have a structure. In this structure, there is a sentence after the verb: Dorothy thinks witches are dangerous. In this structure, the sentence "Witches are dangerous" appears in a larger sentence. Therefore, a sentence can be defined recursively (very roughly) as a structure, including a noun phrase, a verb and an optional other sentence. This is actually just a special case of recursive mathematical definition.

This provides a way to understand language creation-an infinite number of grammatical sentences-because it immediately predicts that sentences can be of any length: Dorothy thinks that Toto suspects what the Tin Man said ... besides recursively defined sentences, there are many structures, so a sentence can embed instances of one category into another in many ways. Over the years, on the whole, language has proved to be suitable for this kind of analysis.

Recently, however, Daniel Everett challenged the generally accepted view that recursion is the basic attribute of human language according to his views on Chinese in pilar. Andrew nevins, David Peset and Celine Rodriguez are among many people who oppose this view. In any case, literary self-citation can be regarded as different from mathematical or logical recursion.

Recursion not only plays a vital role in grammar, but also in natural language semantics. For example, the word and can be understood as a function, which can be applied to the meaning of sentences to create new sentences, and can also be used to the meaning of noun phrases and verb phrases. It also applies to intransitive verbs, transitive verbs or ditransitive verbs. In order to provide it with an appropriate and flexible single representation, it is usually defined that these different types of meanings can be used as parameters. This can be achieved by defining it for a simple case, in which it combines sentences and then recursively defines other cases according to this simple case.

Recursive grammar is a kind of formal grammar containing recursive generation rules.

Recursive humor

Recursion is sometimes used humorously in textbooks of computer science, programming, philosophy or mathematics, usually by giving a definition of cycle or self-reference, in which the assumed recursive step is not closer to the baseline condition, but leads to infinite regression. It is not uncommon for such a book to include a joke entry in the vocabulary, which is roughly as follows:

Another joke is "to understand recursion, you must understand recursion." In the English version of Google Web search engine, when searching for "recursion", the website will prompt "You mean: recursion?" Another form of Andrew Plotkin is as follows: "If you already know what recursion is, remember the answer. Otherwise, find someone closer to Douglas hofstadter than you; Then ask him or her what recursion is. "

Recursive acronyms can also be examples of recursive humor. For example, PHP stands for "PHP hypertext preprocessor" and WINE stands for "WINE is not an emulator." And GNU stands for "GNU is not Unix".

In mathematics

Recursive definition set

Example: Natural Numbers

Natural numbers give a typical example of recursively defining a set:

0 is a natural number;

If n is a natural number, then n+ 1 is also a natural number;

The set of natural numbers is the smallest set that satisfies the first two attributes.

Example: a set of truly attainable propositions

Another interesting example is the set of all "truly reachable" propositions in the axiomatic system.

If a proposition is an axiom, it is a truly attainable proposition.

If a proposition can be obtained from a truly reachable proposition through inference rules, then it is a truly reachable proposition.

The truly reachable proposition set is the smallest proposition set that satisfies these conditions.

This set is called "true reachable proposition" because in the non-constructive method of mathematical foundation, the set of true propositions may be larger than the set recursively constructed by axioms and inference rules. Finite subdivision rule

Finite subdivision rules are recursive geometric forms, which can be used to create fractal-like images. The subdivision rule starts with a group of polygons marked by a finite number of labels, and then subdivides each polygon into smaller marked polygons in a way that only depends on the labels of the original polygons. This process can be iterative. The standard "middle third" method of creating Cantor set is subdivision law, and the subdivision of center of gravity is also subdivision law. Function recursion

A function can be defined in part by itself. A common example is Fibonacci sequence: F(n) = F(n? 1) + F(n？ 2)。 In order to make such a definition useful, it must introduce a non-recursive definition value, in which case, F(0) = 0 and F( 1) = 1.

A famous recursive function is Ackerman function, which is different from Fibonacci sequence. Without recursion, it can't be expressed. Proof involving recursive definition

As mentioned above, the application of standard case proof technology to recursively defined sets or functions will lead to structural induction, which is a powerful extension of mathematical induction and widely used in mathematical logic and computer science. Recursive optimization

Dynamic programming is an optimization method, which restates multi-stage or multi-step optimization problems in recursive form. The key result of dynamic programming is bellman equation, which writes the early (or earlier) value of the optimization problem into the late (or later) value. Recursive theorem

In set theory, this is a theorem to ensure the existence of recursive definition function. Given a set x, an element a in the set x and a function f: x->; X, the theorem shows that there is a unique function f: n->; X(N represents a set of natural numbers containing 0) makes F(0)=a, F(n+ 1)=f(F(n)) satisfied (for any natural number n).

Uniqueness proof

Take two functions f: n-> X and g: n-> X to satisfy:

F(0)=a

G(0)=a

F(n+ 1)=f(F(n))

G(n+ 1)=f(G(n))

Where a is an element in the set X.

Mathematical induction can prove that F(n)=G(n) exists for all natural numbers:

Baseline condition: when n=0, the equation F(0)=a=G(0) holds;

Recursive step: assuming that F(k)=G(K) holds when k∈N, then F(K+1) = F (f (k)) = F (g (k)) = G (k+1), then F (k).

Through induction, F(n)=G(n) (where n∈N).

In computer science,

A common simplification method is to decompose a problem into subproblems of the same type. As a computer programming technology, this is called divide-and-conquer method, which is the key to many important algorithm designs. Divide and conquer is a top-down method, which solves problems by solving smaller and smaller examples. The opposite method is dynamic programming, which is a bottom-up method to solve problems by solving more and more examples until it reaches the required scale.

A classic example of recursion is the definition of factorial function, which is given in C code as follows:

Unsigned integer factorial (unsigned integer n) {undefined

If(n = = 0){ undefined

Returns1;

} else {undefined

Returns the factorial of n * (n-1);

}

}

This function recursively calls itself on a smaller version of the input (n- 1) and multiplies the result of the recursive call by n until the baseline condition is reached, similar to the mathematical definition of factorial.

Recursion in computer programming is an example when a function is defined as a simpler and usually smaller self. Then the solution of the problem is designed by combining the solutions obtained from the simple version of the problem. An example application of recursion is in a parser of a programming language. The biggest advantage of recursion is that you can define, analyze or generate an infinite set of sentences, designs or other data through a limited computer program.

Recursive relations are equations that recursively define one or more sequences, and some specific types of recursive relations can be defined by "solving".

In the field of art

Russian doll or Russian doll is an example of the physical art of recursive concept.

Recursion has been used in painting since Giotto's Stefanesky Triptych was published in 1320. Its central panel contains a statue of a kneeling cardinal Stefaneschi, holding a triptych as a sacrifice.

M.C. Eschers Printing Gallery (1956) depicts a twisted city, which contains a gallery containing pictures recursively, so it is infinite.