This is the 15th day of my participation in Gwen Challenge

Data structures and algorithms – recursion

Master L. Peter Deutsch said: To Iterate is Human, To Recurse, Divine. Man understands iteration, god understands recursion. Recursion is, of course, a wonderful way of thinking. For some simple recursive problems, we are always amazed at the ability of recursion to describe the problem and the simplicity of coding, but it is not easy to really understand the essence of recursion and flexibly use recursion to solve the problem. This paper analyzes the ideological connotation of recursion, analyzes the connection and difference between recursion and circulation, and gives the application scenarios and some typical applications of recursion. Eight classical problems including factorial, Fibonacci sequence, Hannotta, access to Yang Hui’s triangle, string palindrome judgment, string full arrangement, binary search and tree depth solution are solved by recursive and non-recursive methods.

To understand recursion

Simply put, a function that calls itself is called a recursive function. This technique is called recursion; To create a recursive function, you must create a termination condition to prevent the function from executing indefinitely. Stack overflow may occur

func recurse(a) {
    //statements
    recurse()
}
recurse()
Copy the code

The following figure shows how recursion works by calling itself repeatedly.

Swift recursive factorial implementation

func factorial(of num: Int) -> Int {
    if num = = 1 {// Termination conditions
        return 1
    } else {
        print("return \(num)* factorial (\(num - 1))")
        return num * factorial(of:num - 1) // Recursion must be decomposed into several smaller subproblems of the same form as the original problem, which can be solved using the same idea of solution}}let x = 4
let result = factorial(of: x)
print("\(x)The factorial is\(result)")

/** "" return 4 * factorial (3) return 3 * factorial (2) return 2 * factorial (1) 4 is 24" "*/
Copy the code

The recursion satisfies three conditions

  1. The solution of a problem can be decomposed into solutions of several problems
  2. The solution of this problem is the same as that of the subproblems after decomposition, except that the data scale is different
  3. There is a condition for recursive termination

Write recursive code

Key point: write the recursive formula and find the termination condition

See above: Swift recursive factorial implementation

function recursion(On a large scale){
    if (end_condition){      // An explicit recursive termination condition
        end;   // Simple scenario
    }else{            // At each step of converting a problem to a subproblem, solve the remaining problems in that step
        solve;                / / passRecursion;// After reaching the deepest point, keep coming back}}Copy the code

Notice the recursion

  1. Recursive code is wary of stack overflows

In real software development, we encounter many problems when writing recursive code, such as stack overflows. A stack overflow can cause a systemic crash, and the consequences can be severe

Solution: Add a variable to the recursive function to calculate the number of recursions, also known as the maximum depth of the way to solve the problem

  1. Be wary of double counting in recursive code

To avoid double-counting, we can use a data structure (such as a hash table) to store the solved f(k). When I recursively call f(k), let’s see if I’ve solved it. If it is, it returns the value directly from the hash table without double-counting, thus avoiding the problem we just described.

public func f(n: Int) -> Int {
    if (n = = 1) { return 1}
    if (n = = 2) { return 2}
    
    // hasSolvedList can be understood as a Map with key n and value F (n)
    if (hasSolvedList.containsKey(n)) {
        return hasSolvedList.get(n);
    }
    
    var ret = f(n-1) + f(n-2);
    hasSolvedList.put(n, ret);
    return ret;
}
Copy the code

Recursion is still a little difficult to understand, this article from the morning to the evening, a little understanding and experience, refer to many articles and blogs;

other

Today is the 15th day for me to learn SWIFT. All the codes involved in these 15 days are written in SWIFT. In this process, I am constantly adapting to the new syntax and norms brought by SWIFT. Anyway, I am very happy to finish my first 15-day study plan; Next, I will go deep into swift project development and strive to develop a pure SWIFT project. The project has not been decided yet. If you have a good project recommendation, please leave a message and tell me!

Come on, sun arch a pawn!

reference

www.srcmini.com/2786.html

www.imangodoc.com/10765.html

Blog.csdn.net/sinat_38052… (recommended)