In this article you will learn

Why write this article

  1. “Recursive” algorithm should be one of the most classical algorithms for a programmer, and it is more and more messy, many complex algorithms are also used in the implementation of recursion, such as depth first search, binary tree traversal, etc..
  2. Recursion-related topics are often asked in interviews (deep copy, object formatting, array flattening, step questions, etc.)
  3. There is a requirement in the recent project, fission sharing, but it will give rebates not only to the sharers, but also to the final sharers, but only to level 4 distribution (recursion is also used, explained in this article).

Koala is dedicated to sharing the complete Node.js technology stack, from JavaScript to Node.js, to back-end database. Wish you become an excellent senior Node.js engineer. [Programmer growth refers to north] Author, Github blog open source project github.com/koala-codin…

What is the recursive algorithm

Wikipedia: Recursion is using itself inside the definition of a function. A function with this definition is called recursion. This may sound like a recipe for infinite repetition, but as long as you define it properly, it won’t. In general, the definition of a recursive function has two parts. First of all, there has to be at least one bottom line, which is a simple line, and beyond that, recurse.

My own simple understanding of recursion is that you call yourself, recursively, and pay attention to the bounds.

An interesting picture:

Recursion algorithm idea explains uses and notes

When to use recursion?

Take a look at a small example of what happened during the National Day holiday to take you into recursion. 11 holidays lined up to collect the tickets to the railway station, the ticket line for many people, this time there are always some friend said to jump the queue time collect the tickets, I have very far away, find themselves far from collect the tickets mouth is more and more, I want to know what I am now in the super position (the premise: no someone cut in line in front of the ticket), using a recursive thinking what should we do?

Satisfies the condition for recursion

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 previous example where you want to know where you are in line, you need to know that the question of your own row can be broken down into the sub-question of everyone’s row.

  1. The sub-problems after the decomposition of this problem, except the data size is different, the solution idea is exactly the same

For example, if you want to know where you are in line, the way you solve for what row you are in is exactly the same way that people in the previous row solve for what row they are in.

  1. There are recursive termination conditions

For example, if you want to know where you are in the first row, the person in the first row knows what row they are in without asking anyone else, that is, f(1) = 1. This is the termination condition of recursion, and finding the termination condition will start the process of “return”.

How do I write recursive code? (After the above conditions are met and recursion is confirmed)

Two key things to remember:

  1. Write the recursion formula (note the branch recursion)

  2. Finding termination conditions

Analysis of ticket queuing example (Single branch level recursion)

If I want to know what line MY seat is in, I ask the person in front of me. The person in front of me plus one is the person’s current position in the queue. The person in front of you wants to know how to move on. I wonder if I’ve figured out the recursion formula.

f(n) = f(n-1) + 1
//f(n) is my current layer
//f(n-1) is the current layer of the person in front of me
// +1 is my front layer and my layer
Copy the code

Let’s look at another example of walking steps (Multi-branch parallel recursion)

Learn how to analyze and write recursive code, using the most classic step by step example.

Suppose there are n steps and you can take one or two steps at a time. How many ways can you take n steps? Solve it programmatically.

According to the above key points, first find the recursive formula: according to the first step can be divided into two categories, the first type is the first step to take a step, the second type is the first step to take two steps. So n steps = (1 step followed by n-1 step) + (2 steps followed by n-2 steps). The recursion formula is:

f(n) = f(n-1)+f(n-2)
Copy the code

So if we have the recursive formula for step 2 and we have the recursive formula for step 2, we’re almost halfway through the recursive code. Let’s look at the termination condition. When we have a step, we don’t have to keep recursing, there’s only one way to go. So f (1) = 1. Is this recursive termination condition sufficient? We could do it with smaller numbers like n equals 2, n equals 3.

When n is 2, f of 2 is equal to f of 1 plus f of 0. If there is only one termination condition f(1)=1, then f(2) is unsolvable. So in addition to the recursive termination condition that f(1)=1, we also have f(0)=1, which means there’s a way to go to 0 steps, but that doesn’t seem logical. So, we can use f(2)=2 as a termination condition, which means that we can take two steps, and there are two ways to do it, one step or two steps.

So, the recursive termination condition is f(1)=1, f(2)=2. At this point, you can take n=3, n=4 to verify that this termination condition is sufficient and correct.

We combine the recursive termination condition with the recursive formula we just derived:

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

And then it’s converted into code based on the final recursive formula

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

Considerations when writing recursive code

The above mentioned two examples (to eleven lined up to collect the tickets to the station, walk the steps), according to these two examples (choose the reason of these two examples, eleven to lined up to collect the tickets at the station problem of single branch recursion, problem multi-branch parallel recursive walk steps, two examples just right), then we tell me the matters needing attention of the recursion.

1. The burst stack

If the stack size is 1KB, the stack size is 1KB. If the stack size is 1KB, the stack size is 1KB. The code for recursion without stack burst is as follows:

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

The function call uses a stack to hold temporary variables. The data structure of the stack is advanced and then out. Every time a function is called, temporary variables will be encapsulated as stack frames and pushed into the memory stack, and the function will be removed from the stack when it returns after completion of execution. System stack or virtual machine stack space is generally not large. If the data size of the recursive solution is very large, the call level is very deep, and the stack is pushed all the time, there will be the risk of stack overflow.

Write the code this way, for this kind of hypothetical endless queue will certainly appear stack burst situation, modify the code

// Global variable to indicate the depth of recursion.
let depth = 0;

function f(n) {+ + the depth;if (depth > 1000) throw exception;
  
  if (n == 1) return 1;
  return f(n-1) + 1;
}
Copy the code

After modify the code, added to prevent stack and the number of recursive explosion limit, this is a good way to prevent stack explosion, but please note that the limit the number of recursive generally do not limit to 1000, average number of five times, also good 10 times, 1000 times, there is no guarantee that other variables are not deposited in the stack, cannot be computed in advance, There may also be a stack burst problem.

Tips: If the recursion depth is relatively small, you can consider limiting the number of recursions to prevent stack explosion. If the depth is 1000 like this, consider other ways to achieve it.

2. Double counting

Step example, we have previously derived the recursive formula and code implementation. Write it here again:

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

That’s what double-counting is all about, and maybe you don’t understand it, but if you draw a picture of a function being called repeatedly, you’ll get the idea.

If you look at function calls in the diagram, you’ll see that many functions are called multiple times, for examplef(3)To calculate thef(5)You need to calculate firstf(4) 和 f(3)To calculatef(4)You have to calculate itf(3) 和 f(2), this kind off(3)It’s been double-counted many times. Solution. We can use a data structure (note: this data structure can be various, such as js can be usedset.weakMap, or even arrays. Java can also be a variety of hash tables, thinking children can think of which is better oh, after the deep copy example I will also be specific) to store solvedf(k)If the value is returned directly from the hash table, there is no need to repeat the calculation, which avoids the double calculation problem. The specific code is as follows:

let mapData =new Map(a);function walk(n){
    if(n === 1) return 1;
    if(n === 2) return 2;
    // Determine and store values
    if(mapData.get(n)){
        return mapData.get(n);
    }
    let value = walk(n-1) + walk(n-2);
    mapData.set(n,value);
    return value;
}
Copy the code

3. Circular references

A circular reference is a repetition of something that recurses, such as a deep copy of the following:

const target = {
    field1: 1.field2: undefined.field3: {
        child: 'child'
    },
    field4: [2.4.8]}; target.target = target;Copy the code

How to implement deep copy and avoid circular reference in detail in the actual section of the article, please continue to read, buddy.

A little insight into recursive algorithms

Before mentioned the use of recursive algorithm to meet the three conditions, determine to meet the conditions, write recursive code when the key point ((write recursive formula, find the termination condition), this key point has been mentioned three times in the article oh, please remember it, finally according to the recursive formula and termination condition translated into code.

Recursive code, don’t try to use our brains to break down each step of the recursion layer by layer. This will only get more and more annoying. Even the gods can’t do this.

  • Recursive algorithm advantages: the expression of the code is very strong, very simple to write.
  • Disadvantages of recursive algorithm: Recursive algorithm has a stack overflow explosion (stack), a risk repeating calculation, problems such as too much function call will take more (must consider when writing a recursive algorithm of this a few faults), the function of variable storage needs additional stack space, when the recursion depth is deep, need additional will be a lot of memory space, so the recursive with very high space complexity.

Recursion algorithm usage scenarios (several interview questions mentioned at the beginning)

When writing the following practical application scenarios, the idea is the same as before, repeat it (write the recursive formula, find the termination condition).

1. Classic step problem

Step problems have been specifically mentioned in front, here will not be detailed, you can see the above content oh.

2. Level 4 distribution – Find the best referees

Given a user, how to find the user’s final recommendation ID, which says four levels of distribution, the termination condition has been found, only four levels of distribution found. Code implementation:

let deep = 0;
function findRootReferrerId(actorId) {
  deep++;
  let referrerId = select referrer_id from [table] where actor_id = actorId;
  if (deep === 4) return actorId; // Termination conditions
  return findRootReferrerId(referrerId);
}
Copy the code

While the code can be done this way, there is a premise to note:

  1. It’s not in the databaseDirty data(Dirty data may be generated by manually inserting data directly into the test, for example, A recommends B, and B recommends A again, creating an endless loop of references.)
  2. When confirming that the recommender inserts data into the table, be sure to determine whether the previous recommendation relationship between the two already exists.

3. Flatten the array

let a = [1.2.3[1.2[1.4], [1.2.3]]]
Copy the code

And when you flatten an array you’re sometimes asked, what is the level of this nested array? The specific implementation code is as follows:

function flat(a=[],result=[]){
    a.forEach((item) = >{
        console.log(Object.prototype.toString.call(item))
        if(Object.prototype.toString.call(item)==='[object Array]'){
            result=result.concat(flat(item,[]));
        }else{
            result.push(item)
        }
    })
    return result;
}
console.log(flat(a)) // Output result [1, 2, 3, 1, 2, 1.4, 1, 2, 3]
Copy the code

4. Format objects

Object formatting problem, this is generally the background returned to the front end of the data, sometimes need to format the case, the general level is not too deep, do not need to consider the termination condition, see the code

// Changes the formatting object from uppercase to lowercase
let obj = {
    a: '1'.b: {
        c: '2'.D: {
            E: '3'}}}function keysLower(obj){
    let reg = new RegExp("([A-Z]+)"."g");
        for (let key in obj){
            if(Object.prototype.hasOwnProperty.call(obj,key)){
                let temp = obj[key];
                if(reg.test(key.toString())){
                    temp = obj[key.replace(reg,function(result){
                        return result.toLowerCase();
                    })]= obj[key];
                    delete obj[key];
                }
                if(Object.prototype.toString.call(temp)==='[object Object]'){ keysLower(temp); }}}return obj;
}
console.log(keysLower(obj));{a: '1', b: {c: '2', d: {e: '3'}}}
Copy the code

5. Implement a deep copy

const target = {
    field1: 1.field2: undefined.field3: {
        child: 'child'
    },
    field4: [2.4.8]}; target.target = target;Copy the code

The code implementation is as follows:

function clone(target, map = new WeakMap(a)) {
    if (typeof target === 'object') {
        let cloneTarget = Array.isArray(target) ? [] : {};
        if (map.get(target)) {
            return map.get(target);
        }
        map.set(target, cloneTarget);
        for (const key in target) {
            cloneTarget[key] = clone(target[key], map);
        }
        return cloneTarget;
    } else {
        returntarget; }};Copy the code

Deep copy is also a common example of recursion

What happens in each copy:

  • Check whether objects have been cloned in the map
  • Yes, go straight back
  • No, the current object is used as the key and the cloned object is stored as the value
  • Continue to clone

WeakMap is used in this code to prevent stack bursts due to circular references.

WeakMap adds knowledge

We all know that there are many kinds of data storage structures in JS. Why do we use weakMap instead of directly using Map for storage?

A WeakMap object, though, is also a set of key/value pairs, where the keys are weakly referenced. The key must be an object, and the value can be arbitrary.

The concept of weak reference is used when writing Java code or more, but when it comes to javascript, there are not many small friends to use. Many deep-copy codes on the Internet are directly used to store Map to prevent stack explosion — weak reference, after reading this article, you can try to use WeakMap oh.

In computer programming, a weak reference, as opposed to a strong reference, is a reference that cannot be guaranteed that the object it refers to will not be collected by the garbage collector. An object that is referred to only by weak references is considered inaccessible (or weakly accessible) and can therefore be reclaimed at any time.

There’s a circular reference in the deep copy and the step problem is double counting, I think it’s two problems, and the step problem is calculated by the termination condition.

conclusion

That’s all for this article. In fact, I still want to write about complexity, but the space is limited. I will write about complexity separately in the future. The point of this article is to repeat, and don’t mind my nagging, when do you use recursion (think about the pros and cons of using recursion)? How do I write the recursive code? Recursive considerations? Don’t try to figure out complex recursions with your brain. The above points to learn to understand enough to let you deal with most of the interview questions, hey, pay attention to the thought oh (there is a weakMap small knowledge we can learn in detail, but also can be extended to an article). If you have time, you can practice with some recursion problems. See you in the next article!

Refer to the article

Refer to the article

  • Tomorrow night :juejin.cn/post/684490…
  • Code Secret Garden :juejin.cn/post/684490…
  • Recursive learning of geek time

Join us and learn! (Add coder_qi to the front-end communication group to learn)