Recursion and tail recursion
Recursion is simply a function calling itself, and it is widely used in programming languages as an algorithm. The core idea is to transform a large complex problem into a smaller problem similar to the original problem. In general, recursion requires boundary conditions, a recursive forward phase, and a recursive return phase. When the boundary condition is not satisfied, recursively forward; When the boundary conditions are met, the recursion returns.
However, as a qualified programmer, we should also know that recursive algorithms are less efficient than common algorithms such as ordinary loops. Therefore, you should avoid recursion unless there is no better algorithm or there is a particular case where recursion is more appropriate. In the process of recursive call, the system has opened up a stack to store the return point and local quantity of each layer. Too many recursion times will easily cause stack overflow.
In this case, we need to use tail recursion, which means that all recursive calls to a function occur at the end of the function. For tail recursion, there is only one call record, so there will never be a stack overflow error.
For example, let’s implement factorial. If we use normal recursion, the implementation would look like this:
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(5) / / 120
Copy the codeWe need to save up to n call stacks, with complexity O(n), if we use tail recursion:
function factorial(n, total = 1) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5) / / 120
Copy the codeAt this point, only one call stack needs to be saved, with complexity O(1). Through this case, have you begun to understand its essence? I’ll introduce a few examples of common recursive applications, followed by an implementation of the tree outlined in the title of this article.
Common application cases of recursion
1. Array summation
Given the array ARR, find the sum of the arR entries.
function sumArray(arr, total) {
if(arr.length === 1) {
return total
}
return sum(arr, total + arr.pop())
}
let arr = [1.2.3.4];
sumArray(arr, arr[1]) / / 10
Copy the codeThis method passes an array argument and an initial value, the first item of the array, to the function and iterates to sum the array.
2. Fibonacci series
The Fibonacci sequence, also known as the Golden section sequence, refers to such a sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34… In mathematics, the Fibonacci sequence is defined by the following recursive method: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n >=3, n∈ n *) The Fibonacci sequence has direct applications in modern physics, quasicrystal structure, chemistry, etc. Next, we use js to implement a method to find the NTH Fibonacci number:
// The Fibonacci sequence
function factorial1 (n) {
if(n <= 2) {return 1
}
return factorial1(n- 1) + factorial1(n2 -)}// After tail recursion optimization
function factorial2 (n, start = 1, total = 1) {
if(n <= 2) {return total
}
return factorial2 (n - 1, total, total + start)
}
Copy the codeFrom the tail-recursively optimized function, each time the function is called, the updated initial value and the final result are passed in, and the final result is obtained by backtracking.
3. The factorial
Factorials have been mentioned earlier, so please look up if you want to review them.
4. Provincial and municipal multi-level linkage
The essence of the multilevel linkage method of provincial and municipal association is to generate structured data structure, and there are corresponding implementations in Element or ANTD, which will not be introduced too much here.
5. Deep copy
Deep copy examples are familiar, here is a simple implementation idea:
function clone(target) {
if (typeof target === 'object') {
let cloneTarget = Array.isArray(target) ? [] : {};
for (const key in target) {
cloneTarget[key] = clone(target[key]);
}
return cloneTarget;
} else {
returntarget; }};Copy the code6. Ladder climbing
There are n steps, and you can only take one or two steps at a time, and they ask you how many ways to take this step.
n =1; result = 1 --> 1
n =2; result = 2 --> 11 2
n =3; result = 3 --> 111 12 21. If the first step goes1From the above rule, we can find that the remaining steps have n- 1The motorway; If the first step goes2From the above rule, we can find that the remaining steps have n2 -The motorway; So we have f sub n of n- 1) + fn(n2 -) the motorwayfunction steps(n) {
if(n <= 1) {
return 1
}
return steps(n- 1) + steps(n2 -)}Copy the code7. Format the object data
This question is a pen test that I once interviewed Ali. The question is if the server returns nested objects, the case of the object key name is uncertain, if the key name is lowercase.
let obj = {
a: '1'.b: {
c: '2'.D: {
E: '3'}}}let obj = {
a: '1'.b: {
c: '2'.d: {
e: '3'}}}// Code implementation
function keysLower(obj) {
let reg = new RegExp("([A-Z]+)"."g");
for (let key in obj) {
if (obj.hasOwnProperty(key)) {
let temp = obj[key];
if (reg.test(key.toString())) {
// Reassign the modified property name to temp and add a converted property to object obj
temp = obj[key.replace(reg, function (result) {
return result.toLowerCase()
})] = obj[key];
// Delete the previously capitalized key attribute
delete obj[key];
}
// If the property is an object or an array, re-execute the function
if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') { keysLower(temp); }}}return obj;
};
Copy the codeThe specific process and ideas have been written in the code in the comments, you can be interested in their own research.
8. Traversal/delete a directory
The existing Node API does allow you to delete a directory, but fs.rmdir && fs.rmdirsync does not allow you to delete files or subdirectories in the directory, so you need to delete the files in the directory first, and then the folder.
function deleteFolder(path) {
var files = [];
if(fs.existsSync(path)) { // If the directory exists
files = fs.readdirSync(path);
files.forEach(function(file,index){
var curPath = path + "/" + file;
if(fs.statSync(curPath).isDirectory()) { // Recurse if it is a directory
deleteFolder(curPath);
} else { // Delete the filefs.unlinkSync(curPath); }}); fs.rmdirSync(path); }}Copy the code9. Draw fractal graphs
By recursion, we have more freedom in the graphics, but remember, it’s not the best choice.
The array is Flat
Array flattening is essentially expanding a nested array into a single array, as shown in this example:
let a = [1.2.3[1.2.3[1.2.3]]]
/ / into
let a = [1.2.3.1.2.3.1.2.3]
// Concrete implementation
function flat(arr = [], result = []) {
arr.forEach(v= > {
if(Array.isArray(v)) {
result = result.concat(flat(v, []))
}else {
result.push(v)
}
})
return result
}
flat(a)
Copy the codeOf course, this is just one way I implemented it, and there are more ways for you to explore.
Draw a custom style structure tree using recursion
Now that I’ve given you a basic idea of recursion and how it works, I’m going to take you step by step and draw a structure tree using recursion. Effect:
const fs = require('fs')
const path = require('path')
// Traverse the directory/generate the directory tree
function treeFolder(path, flag = '| _') {
var files = [];
if(fs.existsSync(path)) {
files = fs.readdirSync(path);
files.forEach(function(file,index){
var curPath = path + "/" + file;
if(fs.statSync(curPath).isDirectory()) { // recurse
// obj[file] = treeFolder(curPath, {});
console.log(flag, file)
treeFolder(curPath, ' ' + flag)
} else {
// obj['--'] = file
console.log(flag, file)
}
})
// return obj
}
}
treeFolder(path.resolve(__dirname, './test'))
Copy the codeThe test directory created for us is as follows:
Welcome to learn from each other and explore the frontiers of the front end.
More recommended
- Write a mock data server using nodeJS in 5 minutes
- Cartesian product is implemented and applied in javascript
- JavaScript binary tree and binary search tree implementation and application
- With JavaScript and C3 to achieve a turntable small game
- Teach you to use 200 lines of code to write a love bean spell H5 small game (with source code)
- Exploration and summary of front-end integrated solutions based on React/VUE ecology
- How to use gulP4 development project scaffolding
- How to write your own JS library in less than 200 lines of code
- A summary of common JS functions that make you more productive in an instant
- A picture shows you how to play vue-Cli3 quickly
- 3 minutes teach you to use native JS implementation with progress listening file upload preview component
- 3 minutes teach you to use native JS implementation with progress listening file upload preview component
- Developing travel List with Angular8 and Baidu Maps API
- Js basic search algorithm implementation and 1.7 million data under the performance test
- How to make front-end code 60 times faster
- Front End Algorithm series array deweighting
- Vue Advanced Advanced series – Play with Vue and vuex in typescript
- In the first three years, talk about the top five books worth reading