Detailed analysis of classic JavaScript recursion case questions

What is recursion and how does it work?

Let's first look at the definition of recursion:

Recursion is an efficient way to solve problems, in which a function calls itself as a subroutine.

Simply put, the programming technique in which a program calls itself is called recursion. The idea of ​​recursion is to transform a large and complex problem layer by layer into a problem that is smaller in scale than the original problem. After the problem is broken down into sub-problems, recursive calls continue until the sub-problems can be solved without further recursion.

When using recursion, you need to avoid infinite loops. To ensure that recursion works correctly, recursive programs should contain two properties:

1. Bottom cases: Bottom cases are used to ensure that program calls return in a timely manner and do not continue to recurse, thus ensuring that the program can terminate.
2. A recurrence relation that breaks down all other cases into base cases.

A function that calls itself is recursive. Remember to have a termination condition, otherwise it will enter an infinite loop.

1. Sum

(1) Digital summation

    function sum(n){
      if(n===1){
        return n=1
      }
      return n+sum(n-1)
    }
    console.log(sum(5));

Execution Order

5+sum(n-1)
5+4+sum(n-1)
5+4+3+sum(n-1)
5+4+3+2sum(n-1)
5+4+3+2+1

(2) Array summation

        function sum(arr) {
        var len = arr.length
        if (len == 0) {
          return 0
        } else if (len == 1) {
          return arr[0]
        } else {
          return arr[0] + sum(arr.slice(1))
        }
      }
      let arr = [ 1, 2, 3, 4, 5 ]  
      console.log(sum(arr))

Execution Order

1+sum(2,3,4,5)
1+2+sum(3,4,5)
1+2+3(4,5)
1+2+3+4+sum(5)
1+2+3+4+5
1+2+3+9
1+2+12
1+14
15

2. Data transfer tree

        let data = [{
                id: "01",
                pid: "",
                "name": "Lao Wang"
            },
            {
                id: "02",
                pid: "01",
                "name": "Xiao Zhang"
            }
        ]

  function fn(data, rootId = '') {
            const children = [] //define an empty array data.forEach(item => {
                if (item.pid === rootId) { //If each item's pid=rootId is added to the array children.push(item)
                    item.children = fn(data, item.id)
                }
            });
            return children
        }

Use recursive tree transformation to know the value of the root pid before proceeding to the next step, as a starting point.

Execution Order

3. Tower of Hanoi

The following three columns are set as a, b, and c. The goal is to put all the plates in a into column c in order from large to small. Only one plate can be moved at a time.

Implementation ideas:

1. Move n-1 plates from a to b
2. Move n disks from a to c
3. Move n-1 plates from b to c

        function fn(num, start, middle, end) {   
            if(num>0){
                fn(num-1,start,end,middle)
                console.log(start+'====>'+end); 
                fn(num-1,middle,start,end)
            }
           }
              fn(2,'a','b','c')

Let num be the number of plates, start be plate a, middle be plate b, and end be plate c.

For example, the execution order of 2 plates

1. In the first line, bring 2 in and num>0. Execute the first function fn(2-1,start,end,middle). Then execute fn(1-1,start,end,middle). Find that num is not greater than 0. Not only that, look back at fn(2-1,start,end,middle) and output console.log(a===>b).

2. The second line console.log(start+'====>'+end); directly outputs a===>c

3. The third line fn(2-1,middle,start,end) executes console.log(b===>c) and next time fn(1-1,middle,start,end) fails to enter the loop and execution is completed

The execution order is a bit abstract. If you really don’t understand it, just follow the simplest way of thinking. fn(num, start, middle, end) is how we usually play games. The initial diagram

fn(num-1,start,middle,end) Take the second parameter position as the plate to be moved and the fourth parameter position as the moving target. Every time you look at the picture, bring this formula in.

Step 1 fn(num-1,start,end,middle) For example, if there are two plates, a-1 must be placed on b first.

The second step is to put plate a on c and directly output console.log('a===>c')

The third step is to put plate b on c fn(num-1,middle,start,end,)

4. Fibonacci Sequence

The Fibonacci sequence, also known as the golden ratio sequence, was introduced by mathematician Leonardo da Fibonacci using the example of rabbit reproduction, so it is also called the "rabbit sequence". It refers to a sequence of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

        function Fibonacci(n) {
            return n <= 1?1:Fibonacci(n - 1) + Fibonacci(n - 2)
        }

Except for the first two, each time the sum of the previous number and the previous two numbers is equal to the third number.

For example, the number 5. The first term is 3. The first two terms are 2. 3+2=5.

Summarize

This is the end of this article about the detailed analysis of classic JavaScript recursive case questions. For more relevant JavaScript recursive case content, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!