Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Recursion is a super powerful way to solve problems

As A front-end dog facing job hunting, I often tried “recursive solution” with the idea of trying after I dropped A force button in violent iteration A at the beginning of the task.

And then shut down

Over the course of several months I have come to understand —

  • Recursive functions are stored on the stack until the boundary conditions are triggered and the stack starts bouncing and executing functions

  • It’s better to explore the return content from the innermost layer

.

Studying recursion is quite like 🤔

I have read many articles about recursion before, but I always feel that either god is too high than I am too much content is a little difficult to understand, or there are too few examples of a large number of theories to my face a dislike instant meng force 😂

So this article would like to write a small white also can be very comfortable to understand the “recursion” at the same time combined with examples we can first try to write their own recursion solution and then draw a picture if you do not understand to see the solution 🙌

In addition, this article intends to conduct research on recursion methods of different types of questions (as I encounter recursion methods in different types of questions, I will update to this article as a small manual for the future.) Array linked list binary tree… The recursive

After reading this article, you will learn —

  • Use the stack of ideas to easily think of recursion (of course, a simpler recursion 🤣)

  • Use recursion to solve the problem of array loop traversal – the most basic used to start the recursive idea is appropriate 😄

Later, I will use the ideas of this paper to solve more problems

  • Use recursion to solve ordered list merge problems – use recursion to skip complex list traversal for easy answers 😎

  • Use recursion to solve the binary tree problem — the binary tree problem is basically dependent on recursion XD so you want to make a binary tree? First, study the recursion to understand ~🤔

  • Use recursion to solve sorting problems

1. Understand the call stack on which recursive functions reside

Some time ago, I learned that JavaScript’s “execution context stack” can perfectly explain the execution of recursive functions

First of all, let’s talk a little bit about the theory. (The explanation I saw in the previous article makes a lot of sense.)

Recursion is like “look up the dictionary.” We see a sentence and there’s a word we don’t understand and we start looking up the dictionary.

After looking it up, I found some words in the dictionary that I didn’t understand, so I kept looking it up (pushing another recursive function).

. Omit n layers of lookup (i.e., continuous recursive function pushing)

Finally we understand a word (arriving at base case – used to tell recursive functions when to end) ✨

And then use that word to understand the word at the top of the stack (constantly pushing the recursive function off the stack and executing the recursive function return value to the function on the call stack)

Until we understand what this means, the recursive function has done its job

Conclusion: There are two steps to recursion

  • Recursion: Dictionary lookup constantly pushes recursive functions onto the stack

  • Return: “Understand the sentence by retrieving the contents of the dictionary” : push the recursive function off the stack and return the result one by one for subsequent functions to use

Let me give you an example. Let me draw a picture

Use the idea of a call stack to kill recursion

See problem

foo(1);
function foo(i) {
    if (i == 4) {
        return;
    }
    console.log('foo() begin:' + i);
    foo(i + 1);
    console.log('foo() end:' + i);
}
/ / output?
Copy the code

With the call stack very nice! (Don’t think I’m ugly 😢)

And obviously the end result is 1, 2, 3, 3, 2, 1

In fact, it would be much clearer if I had a GIF here but I’m lazy and I’m sure you can imagine it! 😘

According to the direction of the black arrow, the recursive function is pushed and then pushed ~

2. Use recursion instead of loop to solve the array problem

Here are three very simple array operations to help you get a better sense of recursion

Inspired by Freecodecamp, use recursion instead of repetition to create a countdown using recursion to create a sequence of numbers (by the way, give front-end learners a wave of this 333K star treasure learning platform ❤️)

Use recursion to calculate the sum of the first n elements of an array

I’m sure you can beat this in a loop

Because of its simplicity we can use it to get started/practice recursion ideas

/ / the topicWrite a recursive function,`sum(arr, n)`Returns a recursive call array`arr`The former`n`The sum of the elements.Copy the code

recursion

function sum(arr, n){
    if(n <= 0) {return 0;
    }
    else{
        return sum(arr, n - 1) + arr[n - 1];
    }
}
sum([6.6.6.6].3);
Copy the code

Let me draw the recursive call stack

Still do not despise my graph ugly 😂

Create a countdown using recursion

Was that too easy?

One more (ok still very simple 😂)

/ / the topicA function has been defined`countdown`, the function takes one argument (`n`). Functions should be based on arguments`n`Recursive call returns`n` 到 1 ` `An array of contiguous numbers. If the function is less than1The function should return an empty array. For instance, with`n = 5`The calling function should return an array'[5, 4, 3, 2, 1]. Functions must call themselves using recursive functions, not loops of any kind.Copy the code

recursion

Cycle? Don’t use 😐.

Recursive direct SEC kill!

Conventional methods

// countdown to [] countdown to []
// Insert the value into the array when exiting the stack
function countdown(n){
    if(n <= 0) {return [];
    }
    else{
        const countArray = countdown(n - 1);
        countArray.unshift(n);
        // The header is required because the array is in reverse order ~
        // countArray.splice(0, 0, n);
        // This can also achieve the effect of head insertion
        return countArray;
    }
}
countdown(5);/ /,4,3,2,1 [5]
Copy the code

Ternary expressions kill in one line

// 02 More succinct one line of code seconds kill method
// n = 0 returns the value [5,...[]] and then inserts the numbers as the recursive function goes off the stack
function countdown(n){
	return n <= 0 ? [] : [n].concat(countdown(n - 1));
    // return n <= 0? [] : [n, ...countdown(n - 1)]; // The more compact expansion operator ~
}
Copy the code

Let me draw the recursive call stack

Create a sequence of numbers using recursion

Let’s practice one last problem

Here I suggest you open the link above ☝️ to do it yourself!

Drawing call stacks while writing code is fast! Here it is ~😎

recursion

Conventional method

function rangeOfNumbers(startNum, endNum) {
  if(startNum === endNum){
    return [startNum];
  }
  else{
    const countArray = rangeOfNumbers(startNum + 1, endNum);
    countArray.unshift(startNum)
    returncountArray; }};Copy the code

Ternary expressions kill in one line

function rangeOfNumbers(startNum, endNum) {
    return startNum === endNum 
      ? [startNum] 
      :rangeOfNumbers(startNum, endNum - 1).concat(endNum);
      // : [...rangeOfNumbers(startNum, endNum - 1), endNum];  
};

rangeOfNumbers(1.3)
Copy the code

Split it up for aesthetics

Let me draw the recursive call stack

The first two graphs are the conventional way of drawing a ternary expression

Harm! It’s all the same

3. Summary & Problems that can be solved recursively

The recursion covered in this article is the most basic recursion, but to do a good job, you must do a good job!

We need to understand the basic recursion idea thoroughly before we move on to more complex problems

After learning recursion method can try to solve the problem type —

(Updated)

easy

  • 226. Flip the binary tree

  • 206. Reverse linked lists

It is recommended to see this GIF problem solving read do not understand my own eat it satisfied 🍉

var reverseList = function(head) {
    // The "pass" process
    if(head === null || head.next === null) {return head;
    }
    let newHead = reverseList(head.next);// Pass in the head. Next subproblem
    // The node returned after the topmost function(node at the end of the list) is assigned to newHead
    // The process of "return"
    head.next.next = head;
    head.next = null;
    return newHead;
};
Copy the code

  • 25. Merge two sorted lists

  • Sword refers to Offer 10-II. Frog jump step problem

It’s a little bit of a stretch to do it recursively, but this is actually a dynamic programming problem XD

  • Interview question 08.06. Hannotta question

medium

Anyway, these are the most basic, most basic recursive problems

You get the idea of the recursive call stack above and it’s easy to understand how they work but —

Can you actually get a problem and do it recursively and figure out what the inner operation looks like? Not according to this article…

Say to still have to do a problem to think more so!