current position:Home>Fried cold rice series 5: recursion in JavaScript?

Fried cold rice series 5: recursion in JavaScript?

2022-04-29 20:15:42MaybeIsAdog

Form writing habits together ! This is my participation 「 Nuggets day new plan · 4 Yuegengwen challenge 」 Of the 7 God , Click to see the event details .

Preface

The Gengwen challenge in April was so voluminous , It happens to be the busiest time for the company to catch up with the May Day holiday , Every day is too busy to fly , Not to mention the time to write an article . But the old saying goes : Time is like a sponge , There's still a squeeze . see , Hurry up, slow down, or continue to write 6 The article , If you are interested, you can slide to the bottom of the article to see Excellent article in the past

Today is the last working day of the holiday , This activity will be finished before the last one , At that time, it was written in this activity 7 An article , I have completed the first level challenge , It's not easy , Remember to read a little like it !^_^

background

There are no old rules this time , Background none , But we still have to gossip a few words to get into the subject . That explains why the topic of this article is talking about recursive ? I mainly wrote an article on hydrology before , Now it's time to pay the bill ; There is also the recent review , Want to get a deeper understanding of what is recursive recursive What the hell is that? ? Um. ? It feels the same , Then change to another one , recursive How to use it , Commonly used recursive What's in the scene ?

Okay , Don't talk much , Please take a look at the following →

recursive

What is recursion ?

In the program , recursive The function itself calls itself directly or indirectly . recursive It can't be called an algorithm , But it should be understood as a programming skill in line with human problem-solving logic . For example, common problems in Mathematics : Fibonacci sequence 、 Climb the stairs 、 Hanoi Tower and other issues , They can all use the idea of recursion to solve the problem and finally get the answer .

How to understand recursion ?

To understand recursive , Then you must know what is Stack , After all, recursion takes advantage of Stack This data structure to solve the problem . What is Stack Well ? First look at the picture below , It can well express the operation rules of the stack ↓

image.png

A stack is a data structure , A special linear table that can only be inserted and deleted at one end . It stores data according to the principle of "first in, second out" , The first to enter is put at the bottom of the stack ( Also known as Into the stack ), The incoming data is placed on the top of the stack , When you need to read data, pop up the data from the top of the stack ( Pop up can also be called Out of stack or out of stack ).

Okay , Understand the concept , Now let's understand recursion →

Actually recursive It's no different from ordinary function calls , It's just recursive Usually you can't get the results immediately , It's about going through a hang 、 Push 、 The process of getting out of the stack can solve the problem . Let's use the classical Fibonacci sequence to demonstrate the process of recursion , as follows :

Fibonacci sequence Also known as “ Rabbit Series ”, It's such a sequence of numbers :1,1,2,3,5,8,13,21,34,55,89...

//  Fibonacci sequence : 1 1 2 3 5 8 13 21 34 ... 
//  Start with the third item , The value of the latter item is the sum of the first two items 

 The first one is : 1 ..............................1
 The second item : 1 ..............................1                 
 The third one : 1 + 1 ..........................2
 Item four : 1 + 2 ..........................3
 Item 5 : 2 + 3 ..........................5
 Item 6 : 3 + 5 ..........................8
 The first n term : (n - 2) + (n - 1) ...............n
 Copy code 

Convert to graph , As shown in the figure below : image.png

Translate the above analysis into code , as follows :

function fibonacci(n) { 
    if (n <= 2) { //  Termination conditions 
        return 1; 
    } 
    return fibonacci(n - 2) + fibonacci(n - 1); 
}
fibonacci(6); // 8
 Copy code 

Execute the above code to find the second N A Fibonacci number , Just looking at the code and analysis may not be clear enough , The following is the analysis of section 6 How is the value of the term obtained , Pictured :

image.png

analysis : First, execute fibonacci(6) An execution context will be generated when , return 3 + fibonacci(5); Then you need to call fibonacci(5) Regenerate into an execution context , return 2 + fibonacci(4); Then you need to call fibonacci(4) Regenerate into an execution context , return 2 + fibonacci(3); Then you need to call fibonacci(3) Regenerate into an execution context , return 1 + fibonacci(2); Then perform fibonacci(2) and fibonacci(1); because fibonacci(1) At the top of the stack , There's no need to run down , Start popping up , Return results 1, And then it pops up fibonacci(2), And return the result 1 Give the execution context fibonacci(3);fibonacci(3) Execution is 1 + 1 = 2, At the top of the stack, you don't need to execute, so you pass the result to fibonacci(4),fibonacci(4) Execution is 1 + 2 = 3, Also down , We finally reached fibonacci(6) eject , The final result is 8.

This is the execution process of Fibonacci sequence , Because the first two items are fixed , So set it as the termination condition , Then we will calculate the number of... By analogy N Item value ( Be careful : Not the first N Sum of items !!!), Finally, I got the second N The value of the term is equal to the sum of the first two terms , namely (n-2) + (n -1).

Recursive elements

Understand the above example , Then you can know from above , The elements that recursion needs to meet mainly include the following two conditions :

  1. Call yourself
  2. There must be an end condition

Here are some questions to ask , Now that recursion knows , What kind of problem is it to solve ? In fact, recursion is the idea of solving complex problems , For example, you have to calculate 1~100 The sum of the numbers , Do you use for One cycle after another , But if you use recursion, you just need to set a termination condition for it , Let it call itself and you can get the final result . as follows :

//  Will seek 100 Convert to seek 99 
//  Will seek 99 Convert to seek 98 
// ... 
//  Will seek 2 Convert to seek 1 
//  seek 1 The result is 1 
//  namely :sum(1) yes 1 

function sum(n) { 
    if (n == 1) { 
        return 1; 
    } 
    return sum(n - 1) + n; 
} 
var num = sum(100); 
console.log(num); // 5050
 Copy code 

Recursive practice

Come on , Saying without practicing the fake trick , Let's try water with a few examples , as follows :

  1. Find the factorial ! The analysis and code are as follows :
  • 1! .............1
  • 2! .............1! * 2
  • 3! .............2! * 3
  • ...
  • n! .............(n-1)! * n
function factorial(n) { 
    if ( n == 1) { 
        return 1; 
    } 
    return factorial(n - 1) * n; 
} 

// 5! = 1 * 2 * 3 * 4 * 5 
console.log(factorial(5)); // 120
 Copy code 
  1. Exponentiation ! The analysis and code are as follows :
  • 1 Of m Power 1 * 1^(m - 1) = 1^m = 1
  • 2 Of m Power m individual 2 Multiply 2 * 2^(m - 1) = 2^m
  • ...
  • n Of m Power m individual n Multiply namely n * n^(m - 1) = n^m
  • Of each number 1 The power is equal to itself , Such as 2^1 = 2; 3^1 = 3 etc.
function power(n, m) { 
    if (m == 1){ 
        return n; 
    } 
    return power(n, m-1) * n; 
} 

console.log(power(4,3)); // 4 * 4 * 4 = 48
 Copy code 
  1. Finally, let's talk about a common problem in practical projects , Turn a tiled array into a tree , as follows :

The data set is :

const arr = [
    {id: '1', parentId: 'root', name:'1'},
    {id: '1-1', parentId: '1', name:'1-1'},
    {id: '1-2', parentId: '1', name:'1-2'},
    {id: '1-1-1', parentId: '1-1', name:'1-1-1'},
    {id: '1-1-2', parentId: '1-1', name:'1-1-2'},
    {id: '1-2-1', parentId: '1-2', name:'1-2-1'}
];

function getTreeData(data, pid) {
    let copyData = JSON.parse(JSON.stringify(data));
    let arr = [];
    for (let i = 0; i < copyData.length; i++) {
        if (copyData[i].parentId == pid) {
            copyData[i].children = getTreeData(copyData, copyData[i].id);
            arr.push(copyData[i]);
        }
    }
    return arr;
}

const tree = getTreeData(arr, 'root');
console.log('tree', tree);
 Copy code 

thus , recursive The relevant knowledge is introduced , I hope the above examples can help each other better understand recursive This idea . In the actual project, it is practical to recursive My thoughts are not much , This is what is often said , An interview is an interview , Work is work . The time complexity of the algorithm will be considered in the work , At that time recursive The way is not so good , The performance is not particularly good , Take the above example to convert tile data into tree structure data , In fact, other methods will be used in the project , It's just that what we're talking about here is recursive , Just use recursive Think to demonstrate .

The end of this activity is April , It's really not easy , Fortunately, I was able to finish the challenge before the end , The following will also continue to be more civilized , Finally, I wish you all a happy May Day , Pay attention to the epidemic situation !

xdm Look at the text so far , Give a compliment before you go ,3Q^_^

Excellent article in the past

Afterword

partners , If you think this article is of some help to you , Point or focus on walking ^_^ . In addition, if there are problems or incomprehensible parts in this article , Welcome to comment in the comment area and point out , Let's discuss and encourage .

copyright notice
author[MaybeIsAdog],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/04/202204292015330093.html

Random recommended