What is Recursion? What is the popular explanation of recursion

Recursion, that is, calling oneself in the process of running. The conditions that constitute recursion:1

The sub-question must be the same as the original question, and be simpler; 2.It can't be called indefinitely, there must be an outlet, reduced to non-recursive condition processing. in mathematics and computer science.

, recursion refers to a class of objects or methods defined by a simple basic case (or cases) and stipulates that all other cases can be reduced to their base case. For example, the following is a recursive definition of someone's ancestor: A person's parents are his ancestors (basic case).

Someone's ancestors have parents who are also someone's ancestors (recursive step). Fibonacci sequence, also known as the Split sequence.

refers to such a series of numbers ...i[1] The Fibonacci sequence is a classic case of recursion: a recursive relationship is when an entity establishes a relationship with itself.

fib(0) = 1 [base case] fib(1) = 1 [base case] integer > 1 for all n: fib(n) = (fib(n-1) + fib(n-2)) recursive definition] although there are many mathematical functions.

can be recursively represented, but in practice, the high overhead of recursive definitions is often prohibitive. For example: factorial.

1) = 1 [Base case] An integer for all n > 1: factorial(n) = (n * factorial(n-1)) Recursive definition] An easy-to-understand mental model that holds that the recursive definition of an object is defined in terms of "previously defined" objects of the same kind. For example:

How can you move 100 chests? Answer: You first move a box and make a note of where it moved to, and then move on to the smaller problem:

How can you move 99 boxes? Eventually, your question will become how to move a chest, and you already know what to do. Such a definition is very common in mathematics.

For example, set theory.

The formal definition of a natural number is: 1 is a natural number, and each natural number has a successor, which is also a natural number. <>

For example, if you are given a key, you stand in front of the door and ask how many doors you can open with this key. Recursion: You open the door in front of you and see that there is another door in the house (this door may be the same size as the door that opened in front of you (static), or the door may be smaller (moving)), you walk over and find that the key in your hand can still open it, you push the door open, and you find that there is another door inside, and you continue to open it.

After a few times, you open a door in front of you and find that there is only one room, and there is no door. You start to go back the way you came, and every time you go back to a room, you count them, and when you get to the entrance, you can tell how many doors you opened with this key. Loop:

You open the door in front of you and you see that there is another door in the house, (this door may be the same size as the door that was opened in front of you (static), or it may be smaller (moving)), you go over and find that the key in your hand can still open it, you push the door open, and you find that there is another door inside, (if the front door is the same, this door is the same, if the second door is smaller than the first door, this door is also smaller than the second door (the same movement, either there is no change, or the same change)), you continue to open the door. Keep going like this. The person at the entrance never waits for you to go back and tell him the answer.

A program that invokes its own programming technique is called recursion. Recursion as an algorithm is inProgramming languagesIt is widely used.

A procedure or function has a method that directly or indirectly invokes itself in its definition or description, and it usually transforms a large and complex problem into a smaller problem similar to the original problem to solve, and the recursive strategy can describe the solution process with only a small number of programs.

The number of repeated calculations required greatly reduces the amount of the program.

The power of recursion lies in defining an infinite set of objects in finite statements.

In general, recursion needs to have boundary conditions.

Recursive forward segments and recursive return segments. When the boundary conditions are not satisfied, recursively advance; When the boundary conditions are satisfied, recursively returns.

Disadvantages of recursion:

Recursive algorithms. Relatively commonly used algorithms such as ordinary loops are less efficient. Therefore, recursion should be avoided unless there is no better algorithm or in a particular case where recursion is more appropriate.

In the process of recursive calls, the system opens up a stack for each layer of return points, local quantities, etc. to store. Too many recursions can easily cause stack overflows, etc.

The above content reference: Encyclopedia - Recursion.

1. Recursive algorithm concept:

Inside a function or subroutine, directly or indirectly invoke its own algorithm.

2. Basic information:

A recursive algorithm is a subproblem that transforms a problem into a smaller problem of the same kind. A function or procedure is then recursively called to represent the solution to the problem. A procedure or function that directly or indirectly calls itself is called a recursive procedure or function.

Both recursion and iteration are types of loops.

To put it simply, recursion is the repeated call of the function itself to implement the loop. The difference between iteration and ordinary loop is that the variable participating in the operation in the loop is also the variable that saves the result, and the current saved result is used as the initial value of the next loop calculation.

In a recursive loop, when the termination condition is met, it returns layer by layer to end. The iteration uses a counter to end the loop. Of course, in many cases, it is a multi-cycle mixture, depending on the specific needs.

An example of recursion, for example, given an array of integers, uses a halved query to return the index of the specified value in the array, assuming that the array is sorted, and for the sake of description, assuming that the elements are all positive and the length of the array is an integer multiple of 2.

A half-split query is a type of query that is much faster than iterating through all the elements.

int find(int *ary,int index,int len,int value)

if(len==1) last element.

if (ary[index]==value)return index;A successful query returns an index.

return -1;Failed, returns -1

If the length is greater than 1, perform a half-fold recursive query.

int half=len/2;

Check whether the checked value is greater than the last value in the upper half, and if so, recursively query the second half.

if(value>ary[index+half-1])

return find(ary,index+half,half,value);

Otherwise, recursively query the top half.

return find(ary,index,half,value);

The classic example of iteration is the accumulation of real numbers, such as the sum of all real numbers from 1 to 100.

int v=1;

for(i=2;i<=100;i++)

v=v+i;

Recursion is a method of solving a problem by repeatedly breaking it down into sub-problems of the same kind. The recursive method can be used to solve computer science problems with many volts, so it is an important concept in computer science.

The vast majority of programming languages support self-calling of functions, where functions can be recursively called by calling themselves. Computational theory can prove that recursion can completely replace loops, so it is customary to use recursion to implement loops in many functional programming languages. In programming languages that support self-calling, recursion can be done with simple function calls.

Tail recursion is when a recursive function calls itself and passes its value back without adding operations to it. Tail recursion is equivalent to loops, and can be optimized as looping instructions in some languages. As a result, tail recursion does not take up call stack space in these languages.