1. Introduction

  1. The algorithm is king.
  2. Sorting algorithm extensive and profound, predecessors with years or even a lifetime of painstaking efforts to research out of the algorithm, more worthy of our study and deliberation.

Because we’re going to have content and algorithms, and the code is going to be implemented using recursion, so it’s really important to understand recursion.

Definition 2.

  • The way a method or function calls itself is called a recursive call, the call is called a recursion, and the return is called a return. Simply put: call yourself.

Reality example: You take your girlfriend to the cinema this weekend and she asks you, “What row are we in?” It’s too dark to see and count in the cinema. What do you do now?

So you ask the person in front of you what row he is in. You think you can add one to his number and know what row you are in. But the man in front couldn’t see it either, so he asked the man in front of him. And so on, and so on, and so on, and so on, and so on, and so on, and so on, and so on, and so on, and so on, and so on. Until the person in front of you tells you what row they are in, then you know the answer.

Basically, all recursive problems can be expressed by recursive formulas, such as:

f(n) = f(n-1) + 1; // f(1) = 1Copy the code

F (n) means you want to know what row you are in, f(n-1) means the number of rows in front of you, and f(1) = 1 means the person in the first row knows they are in the first row.

With this recursive formula, we can easily change it to recursive code as follows:

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

3. Why recursion? Pros and cons of recursion?

  • Advantages: strong expression of code, simple to write.
  • Disadvantages: high space complexity, stack overflow risk, double calculation, too many function calls will be time-consuming and other problems.

4. What kind of problems can be solved recursively?

A problem can be solved recursively if all three conditions are met.

  1. The solution of a problem can be decomposed into several subproblems.

What are the subproblems? It’s a smaller data scale problem. For example, in the movie theater example, you need to know that the question of which row you are in can be decomposed into a sub-question of which row the people in front of you are in.

  1. Problems and sub-problems, except the data scale is different, the solution idea is exactly the same

For example, in the movie theater, the way you figure out what row you are in is exactly the same way that the person in the front row is trying to figure out what row they are in.

  1. There are recursive termination conditions

In the case of a movie theater, the people in the first row know what row they are in without asking anyone else, so f(1) = 1, and that’s the termination condition for recursion.

5. Recursion FAQ and solutions

  • Beware of stack overflows: You can declare a global variable to control the depth of recursion, thus avoiding stack overflows.
  • Be wary of double counting: Avoid double counting by storing the evaluated values in some data structure.

6. How to implement recursion?

1. Recursive code writing

The key to writing recursive code is to figure out how to break a big problem into smaller problems, write a recursive formula based on that, then refine the termination conditions, and finally translate the recursive formula and termination conditions into code.

2. Understand recursive code

When it comes to recursive code, trying to figure out the whole recursive process is a mistake.

So how do you understand recursive code?

  • If A problem A can be decomposed into subproblems B, C, and D, you can assume that subproblems B, C, and D have been solved.
  • Moreover, you only need to think about the relationship between the two layers of problem A and subproblem B, C and D, instead of thinking about the relationship between subproblems and subproblems and subproblems.
  • It’s a lot easier to understand by masking the recursive details.

So, to understand recursive code, abstract it as a recursive formula, don’t think about layers of calls, don’t try to break down each step of the recursion with your brain.

Example 7.

1. An example of factorial:

function fact(num) {
  if (num <= 1) {
    return 1;
  } else {
    returnnum * fact(num - 1); }} fact(3) // Result is 6Copy the code

The following code can cause an error:

var anotherFact = fact; fact = null; alert(antherFact(4)); / / errorCopy the code

Error because fact is no longer a function.

Using the arguments. The callee

Arguments. callee is a pointer to the function being executed, and arguments.callee returns the pairs being executed. The new function is:

function fact(num){ 
    if (num <= 1){ 
        return 1; 
    }else{ 
        returnnum * arguments.callee(num - 1); // Changed here. } } var anotherFact = fact; fact = null; alert(antherFact(4)); // Result is 24Copy the code

2. Look at another example of a multi-fork tree

Look at the picture first

Leaf node: it is the node with zero depth, that is, the node with no child node. Simply speaking, it is the terminal node on any branch of a binary tree.

Data structure format, refer to the following code:

const json = {
  name: 'A',
  children: [
    {
      name: 'B',
      children: [
        {
          name: 'E',
        },
        {
          name: 'F',
        },
        {
          name: 'G',
        }
      ]
    },
    {
      name: 'C',
      children: [
        {
          name: 'H'
        }
      ]
    },
    {
      name: 'D',
      children: [
        {
          name: 'I',
        },
        {
          name: 'J',}]}]}Copy the code

How do we get all the leaves of the root node?

The recursive code is as follows:

@param {Object} json Object */function getLeafCountTree(json) {
  if(! json.children){return 1;
  } else {
      let leafCount = 0;
      for(let i = 0 ; i < json.children.length ; i++){
          // leafCount = leafCount + getLeafCountTree(json.children[i]);
          leafCount = leafCount + arguments.callee(json.children[i]);
      }
      returnleafCount; }}Copy the code

Recursive traversal is a common method, such as: traversal tree, multi-fork tree, factorial and so on.

8. Article output plan

A series of articles on the beauty of JavaScript data structures and algorithms.

  • 1. The beauty of JavaScript data structures and algorithms – time and space complexity
  • 2. The beauty of JavaScript data structures and algorithms – Linear tables (arrays, queues, stacks, linked lists)
  • 3. The beauty of JavaScript data structures and algorithms – to achieve a front-end routing, how to achieve browser forward and backward?
  • 4. Beauty of JavaScript data structures and algorithms – stack and heap memory, shallow copy and deep copy
  • 5. The beauty of JavaScript data structures and algorithms – recursion
  • 6. Beauty of JavaScript Data Structures and Algorithms – Nonlinear tables (tree, heap)
  • 7. Beauty of JavaScript data structures and algorithms – bubble sort, select sort, insert sort
  • 8. Beauty of JavaScript data structures and algorithms – merge sort, quicksort, Hill sort, heap sort
  • 9. Beauty of JavaScript data structures and algorithms – count sort, bucket sort, radix sort
  • 10. The Beauty of JavaScript Data Structures and Algorithms – Ten classic sorting algorithms
  • 11. The Beauty of JavaScript Data Structures and Algorithms – Highly recommend GitHub’s data structures and algorithms project for front-end learning

If there is any mistake or not precise place, please be sure to give correction, thank you very much.

9. The last

Reference article:

Recursion: How do you find the “final reference” in three lines of code?