An overview of recursion

Recursion, in mathematics and computer science, is the use of the function itself in the definition of a function. Recursion is also more commonly used to describe the process of repeating something in a self-similar way. For example, when two mirrors are approximately parallel to each other, nested images appear in the mirror as infinite recursion. You can also think of it as a self-replicating process.

  • Here’s a language example:

Big male in the room, with time TV watching the past situation. At that moment in the television picture, he is in his room, using the time TV, looking back at the situation. At that time, he was in his room, using the time TV, looking back…

Pseudo code:

Func1 () {Nobita was in his room, using a time TV to look at the past. At that moment in the television picture, he is in his room, using the time TV, looking back at the situation. At that time, he was in his room, using the time TV, looking back... func1() }Copy the code

Recursion in the eyes of a programmer

Recursion is the use of a function’s own methods in its definition.

Recursion has two meanings:

  • A recursive problem must be able to be decomposed into several smaller sub-problems of the same form as the original problem. And these sub-problems can be solved by using exactly the same way of thinking;
  • The evolution of a recursive problem is a process of disassembling the original problem from large to small, and there will be a definite end point (critical point). Once the original problem reaches this critical point, there is no need to break it down into smaller problems. Finally, starting at this critical point, the solution to the small problem is reversed and the original problem is solved.

Here’s an example of using recursion to find n factorial:

The code:

func factorial(_ n: Int)->Int {
      if 1 == n {
          return n;
      } else {
          return factorial(n-1) * n
      }       
 }
Copy the code

Here we pass in 5, and we expand it as follows:

Factorial is simplified to the factorial f (5) = f (4) = > > 5 * 5 * f * f (3) (4) = > 5 * f (4 * f * f (2) (3)) = > 5 * f (4 * f (3 * f (2 * f (1)))) = > 5 * f(4 * f(3 * f(2 * 1)) => 5 * f(4 * f(3 * 2)) => 5 * f(4 * 6) => 5 * 24 => 120Copy the code

The graph is simplified as follows:

So if you look at the picture and think about recursion, you go down, and then you go back, and the point of return is when you reach the termination condition.

The basic idea of recursion is to solve large problems by turning them into small, identical subproblems. In function implementation, because a big problem is the same problem as a small problem, the solution to a big problem is the same as the solution to a small problem. This leads to the function calling itself, and this is where recursion is defined.

A recursively solving function must have an explicit termination condition, otherwise it will result in infinite recursion. To sum up, the implementation of recursion consists of two parts, one is the recursion body, and the other is the termination condition.

Recursive algorithm idea

The recursive mathematical model is actually mathematical induction, and this proof method is the most commonly used method to solve the sequence problem in high school. Now, let’s briefly review mathematical induction by way of a problem.

A common question is to prove that a statement is true when n is equal to any natural number.

When using mathematical induction, the proof is divided into the following 2 steps:

  1. Prove that the proposition is true when n = 1;
  2. Assuming that this is true for n = m, then try to deduce that this is true for n = m + 1.

Similar to mathematical induction, when solving a problem with a recursive algorithm, we need to work around these two steps:

  1. When you have a big problem, how do you break it down into smaller, same problems?
  2. When you take the problem through multiple rounds of decomposition, the end result, which is the definition of termination conditions.

Therefore, when a problem simultaneously satisfies the following two conditions, it can be solved recursively:

  1. It can be disassembled into sub-problems with the same ideas except for data size.
  2. Termination conditions exist.

The recursion case

1. The binary tree is traversed in the preceding order, as shown in the figure below:

Steps to solve the problem:

  • For any node in the tree, print that node first, then pretraverse its left subtree, and then pretraverse its right subtree.

The code is as follows:

func preOrderTraverse(_ root: TreeNode?) Print ("node:(rt.val)") preOrderTraverse(rt.left) {// let rt = root else {return} preOrderTraverse(rt.right) }Copy the code

2. The hannota problem is a puzzle toy derived from an ancient Indian legend. Mahama made three diamond pillars when he created the world, and on one pillar were stacked 64 gold disks in ascending order of size. Mahabrahman ordered the Brahmins to rearrange the discs on another pillar in order of size, starting from below, and stipulated that the discs could not be enlarged on the smaller discs and that only one disc could be moved at a time between the three pillars.

Steps to solve the problem:

  • Let’s say that n is equal to 1, and I have one plate, and it’s easy, just take it out of A and put it on C;
  • What if n is equal to 2? At this point we need to use B, because the small plate must always be on top of the big plate, a total of 4 steps.

What if n is greater than 2? So the idea is the same, let’s think of the n plates as two parts, one part with 1 plate, and the other part with n minus 1 plates.

So how do n minus one plates get from A to C?

Notice that when you think about this problem, the original problem of moving n plates from A to C becomes the problem of moving n-1 plates from A to C, and so on, until it becomes the problem of moving one plate. That’s the idea of divide and conquer.

And a common way to implement divide-and-conquer is recursion. It is not difficult to find that if the original problem can be decomposed into several smaller sub-problems with the same structure as the original problem, it can often be solved by recursive method. Specific solutions are as follows:

  • When n = 1, I just move the plate from A to C;

  • When n > 1,

    • First move the top n-1 plates from A to B (subproblem, recursion);
    • Then move the largest dish from A to C;
    • Move n – 1 plates from B to C (subproblem, recursion).

The code is as follows:

class Solution {
   func hanota(_ A: inout [Int], _ B: inout [Int], _ C: inout [Int]) {
        
        let n = A.count
        move(n, &A, &B, &C)
​
    }
    
    func move(_ n:Int,_ A: inout [Int], _ B: inout [Int], _ C: inout [Int])       {
          if n == 1{
              C.append(A[A.count-1])
              A.removeLast()
              return
          }
          else{
              move(n-1,&A, &C, &B)
​
              C.append(A[A.count-1])
              A.removeLast()
​
              move(n-1,&B, &A, &C)
          }
    }
    
}
Copy the code

conclusion

The core idea of recursion is to solve large problems by transforming them into small, similar sub-problems.

In function implementation, because the way to solve a big problem is often the same as the way to solve a small problem, the situation arises when the function calls itself. In addition, the problem solving function must have an obvious end condition, so that it does not produce infinite recursion. Recursion is widely used in many data structures and algorithms, such as divide-and-conquer strategy, quicksort and so on.

reference

recursive

Diagram of Hannott tower