1. Recursion
Recursion, in mathematics and computer science, refers to the use of a function itself in the definition of a function
Inside a function, other functions can be called. A function is recursive if it internally calls itself
Its core idea is to transform a large and complex problem into a smaller problem similar to the original problem to solve.
In general, recursion requires boundary conditions, a recursive forward phase, and a recursive return phase. When the boundary conditions are not satisfied, recursively advance; when the boundary conditions are satisfied, recursively return
The following implements a function pow(x, n) that computes x raised to the nth power
Use the iterative method as follows:
function pow(x, n) { let result = 1; // In the loop, multiply result n times by x for (let i = 0; i < n; i++) { result *= x; } return result; }
Use recursion as follows:
function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); } }
When pow(x, n) is called, the execution splits into two branches:
if n==1 = x / pow(x, n) = \ else = x * pow(x, n - 1)
That is, pow calls itself recursively until n == 1
To compute pow(2, 4), the recursive variant goes through the following steps:
- pow(2, 4) = 2 * pow(2, 3)
- pow(2, 3) = 2 * pow(2, 2)
- pow(2, 2) = 2 * pow(2, 1)
- pow(2, 1) = 2
So recursion reduces the function call to a simpler function call, which reduces it to a simpler function, and so on, until the result
# tail recursion
Tail recursion, that is, calling itself (or a function that tail calls itself, etc.) at the end of a function. Tail recursion is also a special case of recursion. Tail recursion is a special type of tail call, that is, a recursive function that directly calls itself at the tail
On the basis of ordinary tail calls, tail recursion has two more features:
- The function itself is called at the end
- It can be optimized so that the computation only takes up constant stack space
In the process of recursive call, the system opens up a stack for the return point, local quantity, etc. of each layer to store. Too many recursion times can easily cause stack overflow.
At this time, we can use tail recursion, that is, all recursive calls in a function appear at the end of the function. For tail recursion, since there is only one call record, the "stack overflow" error will never occur
Implement the factorial, if you use ordinary recursion, as follows:
function factorial(n) { if (n === 1) return 1; return n * factorial(n - 1); } factorial(5) // 120
If n is equal to 5, this method needs to be executed 5 times before returning the final calculation expression, so this method needs to be saved every time, which is easy to cause stack overflow, and the complexity is O(n)
If we use tail recursion, as follows:
function factorial(n, total) { if (n === 1) return total; return factorial(n - 1, n * total); } factorial(5) // 120
It can be seen that each time a new function is returned, without the parameters of the previous function, there is no need to store the previous function. Tail recursion only needs to save a call stack, and the complexity is O(1)
# Application scenarios
array summation
function sumArray(arr, total) { if(arr.length === 1) { return total } return sum(arr, total + arr.pop()) }
Finding the Fibonacci sequence using tail recursion optimization
function factorial2 (n, start = 1, total = 1) { if(n <= 2){ return total } return factorial2 (n -1, total, total + start) }
Array flattening
let a = [1,2,3, [1,2,3, [1,2,3]]] // become let a = [1,2,3,1,2,3,1,2,3] // Implementation function flat(arr = [], result = []) { arr.forEach(v => { if(Array.isArray(v)) { result = result.concat(flat(v, [])) }else { result.push(v) } }) return result }
Array object formatting
let obj = { a: '1', b: { c: '2', D: { E: '3' } } } // which translates to the following: let obj = { a: '1', b: { c: '2', d: { e: '3' } } } // Code 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 the object obj temp = obj[key.replace(reg, function (result) { return result.toLowerCase() })] = obj[key]; // Remove previously capitalized key attributes 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; };