# Fried cold rice series 5: recursion in JavaScript?

2022-04-29 20:15:42

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 ↓ 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 ： 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 ： 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^_^

# 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 .