What is recursion? Detailed explanation of recursion in javascript

This article brings you what is recursion? The detailed explanation of recursion in JavaScript has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

1. What is recursion?

The concept of recursion is very simple, "call yourself" (take a function as an example below).

Before analyzing recursion, you need to understand the concept of "call stack" in JavaScript.

2. Pushing and popping the stack

What is the stack? It can be understood that it is a certain area in the memory. This area is likened to a box. If you put something into the box, this action is pushing the stack. So the first thing to put down is at the bottom of the box, and the last thing to put down is at the top of the box. Taking something out of the box can be understood as *pushing it out of the stack.

So we come to the conclusion that we have a habit of taking things from top to bottom. The first thing to put down is at the bottom of the box, and the last thing to get is.

In JavaScript, when a function is called, stack pushing occurs. Pop occurs only when a sentence containing the return keyword is encountered or execution ends.

Let’s take an example. What is the execution order of this code?

function fn1() {
    return 'this is fn1'
}

function fn2() {
    fn3()
    return 'this is fn2'
}

function fn3() {
    let arr = ['apple', 'banana', 'orange']
    return arr.length
}

function fn() {
    fn1()
    fn2()
    console.log('All fn are done')
}

fn()

A series of stack pushing and popping behaviors occurred above:

1. First, the stack (box) is empty at the beginning

2. Function fn is executed, fn is pushed onto the stack first and placed at the bottom of the stack (box)

3. Inside function fn, function fn1 is executed first, and fn1 is pushed onto the stack above fn

4. Function fn1 is executed, and when Go to the return keyword, return this is fn1, fn1 is popped off the stack, and now only fn

5 is left in the box. Return to the inside of fn, after fn1 is executed, function fn2 starts to execute, and fn2 is pushed onto the stack, but after Inside fn2, when fn3 is encountered, fn3 starts to be executed, so fn3 is pushed onto the stack

6. At this time, the order from bottom to top in the stack is: fn3

7. By analogy, when a sentence with the return keyword is encountered inside function fn3, fn3 pops out of the stack after execution and returns to function fn2. fn2 also encounters the return keyword and continues to pop out of the stack.

8. Now there is only fn in the stack. Return to the function fn. After executing the console.log('All fn are done') statement, fn pops out of the stack.

9. Now the stack is empty again.

The above steps are easy to confuse people. Here is the flow chart:

Let’s look at the execution in the chrome browser environment:

3. Recursion

Let’s first look at simple JavaScript recursion

function sumRange(num) {
  if (num === 1) return 1;
  return num + sumRange(num - 1)
}

sumRange(3) // 6

The above code execution sequence:

1. Function sumRange(3) is executed, sumRange(3) is pushed onto the stack, and the return keyword is encountered, but it cannot be popped out of the stack immediately because the call SumRange(num - 1) is sumRange(2)

2. Therefore, sumRange(2) is pushed onto the stack, and so on, sumRange(1) is pushed onto the stack,

3. Finally, sumRange(1) pops the stack and returns 1, sumRange(2) pops the stack, returns 2, sumRange(3) pops the stack

4, so the result of 3 2 1 is 6

Look at the flow chart

So, recursion is also a process of pushing and popping the stack.

Recursion can be expressed as non-recursive. The following is the equivalent execution of the above recursive example

// for 循环
function multiple(num) {
    let total = 1;
    for (let i = num; i > 1; i--) {
        total *= i
    }
    return total
}
multiple(3)

4. Notes on recursion

If the above Modify the example as follows:

function multiple(num) {
    if (num === 1) console.log(1)
    return num * multiple(num - 1)
}

multiple(3) // Error: Maximum call stack size exceeded

There is no return keyword sentence in the first line of the above code. Because there is no termination condition for recursion, it will always be pushed onto the stack, causing a memory leak.

Recursion prone error points

1. No termination point is set

2. Except for recursion, other parts Code

3. When is recursion appropriate

Okay, the above is the concept of recursion in JavaScript.

The following are practice questions.

6. Practice questions

1. Write a function that accepts a string and returns a string. This string is the inversion of the original string.

2. Write a function that accepts a string and compares one character from the front to the back. If the two are equal, return true; if they are not equal, return false.

3. Write a function that accepts an array and returns a flattened new array.

4. Write a function that accepts an object. If the object value is an even number, add them together and return the total value.

5. Write a function that accepts an object and returns an array. This array includes all the values ​​in the object which are strings

7. Reference answer

Reference1

function reverse(str) {
   if(str.length <p>Reference2</p><pre class="brush:php;toolbar:false">function isPalindrome(str){ 
    if(str.length === 1) return true;
    if(str.length === 2) return str[0] === str[1]; 
    if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1)) 
    return false; 
}
var str = 'abba'
isPalindrome(str)

Reference3

function flatten (oldArr) {
   var newArr = [] 
   for(var i = 0; i <p>Reference4</p><pre class="brush:php;toolbar:false">function nestedEvenSum(obj, sum=0) {
    for (var key in obj) { 
        if (typeof obj[key] === 'object'){ 
            sum += nestedEvenSum(obj[key]); 
        } else if (typeof obj[key] === 'number' && obj[key] % 2 === 0){ 
            sum += obj[key]; 
        }
     } 
     return sum;
}
nestedEvenSum({c: 4,d: {a: 2, b:3}})

Reference5

function collectStrings(obj) {
    let newArr = []
    for (let key in obj) {
        if (typeof obj[key] === 'string') {
            newArr.push(obj[key])
        } else if(typeof obj[key] === 'object' && !Array.isArray(obj[key])) {
           newArr = newArr.concat(collectStrings(obj[key]))
        }
    }
    return newArr
}
var obj = {
        a: '1',
        b: {
            c: 2,
            d: 'dd'
        }
    }
collectStrings(obj)

5. Summary

The essence of recursion is that you often have to think about the regular part first. When considering the recursive part, the following are the methods commonly used in JavaScript recursion

Array: slice, concat

String : slice, substr, substring

Object: Object.assign

The above is the detailed content of What is recursion? Detailed explanation of recursion in javascript. For more information, please follow other related articles on the PHP Chinese website!