What is recursion?

#What is recursion?

#The programming technique in which a program calls itself is called recursion.

Recursion as an algorithm is widely used in programming languages. A process or function has a method of directly or indirectly calling itself in its definition or description. It usually transforms a large and complex problem into a smaller problem similar to the original problem to solve. The recursive strategy only A small number of programs are needed to describe the multiple repeated calculations required in the problem-solving process, which greatly reduces the amount of program code. The power of recursion lies in defining infinite collections of objects with finite statements.

Generally speaking, recursion requires boundary conditions, a recursive forward section and a recursive return section. When the boundary conditions are not met, the recursion advances; when the boundary conditions are met, the recursion returns.

Example of nested function calling process

Conditions required to constitute recursion:

1 . The sub-problem must be the same thing as the original problem, and simpler;

2. It cannot call itself unlimitedly, there must be an exit, and it can be simplified to non-recursive situation processing .

In mathematics and computer science, recursion refers to a class of objects or methods defined by one (or more) simple base cases, and stipulates that all other cases can be reduced to their base cases Condition.

In mathematics and computer science, recursion refers to a class of objects or methods defined by one (or more) simple base cases, with the stipulation that all other cases can be reduced to their base cases.

For example, the following is the recursive definition of someone's ancestor: someone's parents are his ancestors (base case).

The parents of someone’s ancestor are also someone’s ancestors (recursive step). Fibonacci Sequence, also known as the golden section sequence, refers to such a sequence: 1, 1, 2, 3, 5, 8, 13, 21.... I [1]

The Fibonacci sequence is a typical case of recursion: the recursive relationship is when the entity establishes a relationship with itself.

Fib(0) = 1 [base case] Fib(1) = 1 [base case] For all integers n > 1: Fib(n) = (Fib(n-1) Fib(n -2)) [Recursive definition] Although many mathematical functions can be expressed recursively, in practical applications, the high overhead of recursive definition is often prohibitive. For example:

Factorial (1) = 1 [Basic case] For all integers n > 1: Factorial (n) = (n * Factorial (n-1)) [Recursive definition] An easy to understand The mental model is that recursive definitions define objects in terms of "previously defined" objects of the same type. For example: How can you move 100 boxes? Answer: You first move a box and note where it is moved, and then move on to the smaller problem: How can you move 99 boxes? Eventually, your problem becomes how to move a box, and you already know how to do it.

Such a definition is very common in mathematics. For example, the formal definition of natural numbers in set theory is: 1 is a natural number, and every natural number has a successor, which is also a natural number.

Droste Effect

The Droste effect is a visual form of recursion. Among the objects the woman is holding is a small picture of herself holding the same object, and then there is an even smaller picture of her holding the same object, and so on.

For another example, if we place a burning candle between two opposite mirrors, we will see a candle in one of the mirrors, and there is a mirror behind the candle, and there is another candle in the mirror. Candles...this is also a manifestation of recursion.

For more related knowledge, please visit PHP Chinese website! !

The above is the detailed content of What is recursion?. For more information, please follow other related articles on the PHP Chinese website!