define

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

Recursion is essentially a loop, but it calls the body of the loop to implement the loop.

The assembly code compiled by the loop itself is similar to the recursion itself.

The movie scene

inception

  • Down into the different into the dream; Up there is back to the original layer.
  • Syncing by voice will go up to the next level
  • There is a copy of each level to the environment and the surrounding people, and several people such as the protagonist travel through different levels of the dream (occurring and carrying changes).

Is it the same as recursion? Third, the protagonist can travel through different dreams, and at the same time take himself and his belongings to different dreams, and bring them back. Just like the arguments in a function, but also some global variables.

Simple recursive example

To calculate n!

N! = 1 * 2 * 3 * 4*…. * n

function recursion(n) {

	if(n <= 1) return 1
    
    	return n * recursion(n);
}
Copy the code

The way recursion ends is called a recursive stack, one layer at a time, and then peeled off, like peeling an onion

Recursive code structure

  • Recursion terminator
  • Process Logic in current level
  • To drill down to the next floor.
  • Reverse the current level status if needed

The main points of

  1. Don’t recurse with human flesh, write code directly after you are familiar with it. Train yourself to think recursively. Don’t write recursion trees by hand.
  2. Find the shortest possible solution and break it down into repeatable problems (repeating subproblems).
  3. The thought of mathematical induction.

In actual combat

Leetcode 70 Climbing stairs

First let’s just read the problem briefly

Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? Note: given n is a positive integer.

Example:

Input: 3

Output: 3

Explanation: There are three ways to climb to the top.

  1. 1 order plus 1 order plus 1 order
  2. 1 order plus 2 order
  3. 2 order plus 1 order

Find repeatability!!

Find repeatability!!

Find repeatability!!

Abstracting out the repetitions of the problem may be difficult at first, but we can draw a recursion tree, or list the repetitions on a piece of paper

Mathematical induction:

So let’s think about n equals 1, n equals 2, n equals 3

N = 1:1

n = 2 : 1 + 1 ; 2

n = 3 : 1 + 1 + 1; 2 + 1; 1 + 2

n = 4 : ……

Of course, you don’t want to go on and on, but in general recursion, you just list the first few terms, and then you can start looking for patterns.

f(3) = f(1) + f(2)

f(4) = f(2) + f(3)

.

All the components are mutually exclusive, and f(1) + f(2) covers all the possibilities of f(3).

f(n) = f(n – 1) + f(n – 2)

show code

var climbStairs = function (n) { if (n === 1) return 1 if (n === 2) return 2 return climbStairs(n - 1) + climbStairs(n - 2)};Copy the code

Of course, this is a crude recursive method, with no optimization and lots of unnecessary calculations.

But that doesn’t mean that recursion is bad.

The problem is not recursion itself, but the use of recursive methods, such as whether necessary results are cached.

The nature of the loop is that there are certain conditions that make it impossible to use a loop to solve a problem.

Leetcode 22 problem bracket generation

First let’s just read the problem briefly

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations.

Example:

Input: n = 3 output: [" ((())) ", "() () ()", "() () ()", "() () ()", "() () ()"]Copy the code

The first character is either ‘(‘, or ‘)’. The first character is either ‘(‘, or ‘)’. The first character is either ‘(‘, or ‘)’

/** * @param {number} n * @return {string[]} */ const res = [] function generateParentthesis(n) {_generate(n, '', res) return res; } function _generate(n, s, Res) {recursion terminator if n <= 0 res.push(s) return let s1 Let s2 = s = s + '(' +') '/ / into the next layer _generate (n - 1, s +' (res) _generate (n - 1, s + ') ', 'res) / / clean up the current state of the layer}Copy the code

At this point, you’ll find that you have the idea, the general recursive code is done.

The next thing you need to do is optimize the code.

  • (and) three at most.
  • Previously used (must be greater than), otherwise not eligible. The number of open parentheses is greater than that of close parentheses
function generateParenthesis(n) {
  const res = []
  var _generate = function (left, right, n, s) {
  // terminator
    if (left >= n && right >= n) {
      res.push(s)
      return;
    }
    // logic & drill down
    if (left < n) _generate(left + 1, right, n, s + '(')
    if (right < left) _generate(left, right + 1, n, s + ')')
  }
  _generate(0, 0, n, '')
  return res;
}
Copy the code