preface

The concept is introduced

The basic concepts and principles of stack have been explained in “article links”, and we will focus on recursive algorithms

1. What is recursion?

• The program calls itself a programming skill called recursion;
• In general, recursion requires boundary conditions, recursive forward sections, and recursive return sections.
• When the boundary condition is satisfied, the recursion returns. When the recursion condition is not satisfied, recursion advances;
• The purpose of recursion is usually to transform a large and complex problem layer by layer into a smaller problem similar to the original problem to solve

2. A popular explanation of recursion

• Maybe you read the definition of recursion still do not understand, then take an example to illustrate: Confucius said “thirty and stand”, you may see this “stand” what is the meaning? Then you continue to search for the explanation of the word “li”, you found Confucius said “stand ceremony”, “I do not know the ceremony, without li also”; Then you don’t know what “li” means; Then we have to continue to search for the meaning of the word “li”. When you understand what “Li” is, you will know what “li” is, and naturally you will know what “thirtysomething” is

The principle of interpretation

The first thing we need to understand about recursion is how it relates to the stack. Let’s take the following code as an example:

int Factorial(int n)
{
    if (0 == n)
    {
        return 1;
    }

    int value = n * Factorial(n-1);

    qDebug() << "n:" << n << " value:" << value;
    return value;
}

Factorial(5);
Copy the code

Recursion versus stack

The recursive process is divided into two steps “recursion” and “return”, corresponding to the two operations on the stack “stack” and “stack”.

1. When n=5, the recursion condition is met, and the stack operation is performed. The specific effect is shown in the following figure

2. When n=4, the recursion condition is met and the operation is performed. The specific effect is shown in the following figure3. When n=3, the recursion condition is met and the operation is performed. The specific effect is shown in the following figure4. When n=2, the recursion condition is met and the operation is performed. The specific effect is shown in the following figure5. When n=1, the recursion condition is met and the operation is performed. The specific effect is shown in the following figure6. When n=0, the recursion condition is not met and the first unstack operation is performed. Factorial(1) is returned7. Continue with the second stack exit operation, taking the result of Factorial(2) to 1Factorial(1)=2 returns8. Continue with the third stack out operation, taking the result of Factorial(3) to 3Factorial(2)=6 returns9. Continue with the fourth stack out operation, taking the result of Factorial(4) to 4Factorial(3)=24 returns10. Continue with the fifth out operation, taking the result of Factorial(5) 5Factorial(4)=120 returns

So the recursion of Factorial of 5 ends

Pros and cons of recursion

• advantages
  • The code is simple
  • Easy to understand
• disadvantages
  • Time and space consumption
  • There may be a stack overflow
  • There may be double counting

Recursion application scenario

• The problem is defined recursively
  • factorial
  • Fibonacci function
• The solution to the problem is recursive
  • Hannotta problem
• The data structure in question is recursive
  • Tree traversal
  • The depth of the tree

For more algorithm learning, please pay attention to my public number

instructions

• In the public number to reply to the “algorithm source” to obtain the source code of ten classic algorithms
• Reply “Algorithm books” in the public account to get the classic introduction algorithm books
• Reply “data structure” in the public number to obtain data structure related source code