- Understanding Recursion, Tail Call and Trampoline Optimizations
- By Thiery Michel
- The Nuggets translation Project
- Permanent link to this article: github.com/xitu/gold-m…
- Translator: Jessica
- Proofreader: PingHGao, Chorer
Understand recursion, tail-call optimization, and trampoline function optimization
To understand recursion, you must first understand recursion. Just kidding, recursion is a programming trick that allows a function to loop through a function that calls itself without using for or while.
Example 1: Sum of integers
For example, suppose we want to find the sum of integers from 1 to I. The goal is to get the following result:
sumIntegers(1); / / 1
sumIntegers(3); // 1 + 2 + 3 = 6
sumIntegers(5); // 1 + 2 + 3 + 4 + 5 = 15
Copy the codeThis is code implemented without recursion:
/ / loop
const sumIntegers = i= > {
let sum = 0; / / initialization
do { / / repeat
sum += i; / / operation
i --; / / the next step
} while(i > 0); // Loop stop conditions
return sum;
}
Copy the codeThe code for recursion is as follows:
/ / loop
const sumIntegers = (i, sum = 0) = > { / / initialization
if (i === 0) { //
return sum; / / the result
}
return sumIntegers( / / repeat
i - 1./ / the next step
sum + i / / operation
);
}
// Even simpler implementation
const sumIntegers = i= > {
if (i === 0) {
return i;
}
return i + sumIntegers(i - 1);
}
Copy the codeThat’s the basis of recursion.
Notice that there are no intermediate variables in the recursive version. It doesn’t use for or do… The while. Thus, it is declarative.
I can also tell you that the recursive version is actually slower than the circular version — at least in JavaScript. But recursion solves not a performance problem, but a expressiveness problem.
Example 2: Sum of array elements
Let’s try a slightly more complicated example, a function that adds up all the numbers in an array.
sumArrayItems([]); / / 0
sumArrayItems([1.1.1]); // 1 + 1 + 1 = 3
sumArrayItems([3.6.1]); // 3 + 6 + 1 = 10
/ / loop
const sumArrayItems = list= > {
let result = 0;
for (var i = 0; i++; i <= list.length) {
result += list[i];
}
return result;
}
Copy the codeAs you can see, the circular version is imperative: you need to tell the program exactly what to do to get the sum of all the numbers. Here is the recursive version:
/ / recursion
const sumArrayItems = list= > {
switch(list.length) {
case 0:
return 0; // The sum of the empty array is 0
case 1:
return list[0]; // The sum of an array of elements, which is the unique element. # Obvious
default:
return list[0] + sumArrayItems(list.slice(1)); // Otherwise, the sum of the array is the sum of the first element + the rest.}}Copy the codeIn the recursive version, instead of telling the program what to do, we introduced simple rules that define the sum of all the numbers in the array. This is much more interesting than the circular version.
If you’re a fan of functional programming, you might prefer the array.reduce () version:
// Reduce version const sumArrayItems = list => list.reduce((sum, item) => sum + item, 0);Copy the codeIt’s shorter and it’s more intuitive. But that’s a topic for another article.
Example 3: Quicksort
Now, let’s look at another example. This time it’s a little more complicated: quicksort. Quicksort is one of the fastest algorithms for sorting arrays.
The sorting process of quicksort: Get the first element of an array, then divide the rest of the elements into arrays smaller than the first element and arrays larger than the first element. The first element retrieved is then placed between the two arrays and repeated for each delimited array.
To implement it recursively, we simply follow this definition:
const quickSort = array= > {
if (array.length <= 1) {
return array; // An array with one or fewer elements is already sorted
}
const [first, ...rest] = array;
// Then separate all elements larger and smaller than the first element
const smaller = [], bigger = [];
for (var i = 0; i < rest.length; i++) {
const value = rest[i];
if (value < first) { / / small
smaller.push(value);
} else { / / bigbigger.push(value); }}// The sorted array is
return [
...quickSort(smaller), // The sorted array of all elements less than or equal to the first element
first, // The first element. quickSort(bigger),// The sorted array of all elements greater than the first
];
};
Copy the codeSimple, elegant and declarative, we can read the definition of quicksort by reading the code.
Now imagine doing it in a loop. I’ll let you think about it, and you’ll find the answer at the end of this article.
Example 4: Get a leaf node of a tree
Recursion is useful when we need to deal with recursive data structures such as trees. A tree is an object with certain values and child attributes; Children in turn contain other trees or leaves (leaves refer to objects without children). Such as:
const tree = {
name: 'root'.children: [{name: 'subtree1'.children: [{name: 'child1' },
{ name: 'child2'},],}, {name: 'child3' },
{
name: 'subtree2'.children: [{name: 'child1'.children: [{name: 'child4' },
{ name: 'child5'},],}, {name: 'child6'}]}]};Copy the codeSuppose I need a function that takes a tree and returns an array of leaves (objects with no child nodes). The expected results are:
getLeaves(tree);
/*[ { name: 'child1' }, { name: 'child2' }, { name: 'child3' }, { name: 'child4' }, { name: 'child5' }, { name: 'child6' }, ]*/
Copy the codeLet’s try it the old-fashioned way, not recursively.
// For trees without nesting, this is a piece of cake
const getChildren = tree= > tree.children;
// For recursion at one level, it becomes:
const getChildren = tree= > {
const { children } = tree;
let result = [];
for (var i = 0; i++; i < children.length - 1) {
const child = children[i];
if (child.children) {
for (var j = 0; j++; j < child.children.length - 1) {
constgrandChild = child.children[j]; result.push(grandChild); }}else{ result.push(child); }}return result;
}
// For two layers:
const getChildren = tree= > {
const { children } = tree;
let result = [];
for (var i = 0; i++; i < children.length - 1) {
const child = children[i];
if (child.children) {
for (var j = 0; j++; j < child.children.length - 1) {
const grandChild = child.children[j];
if (grandChild.children) {
for (var k = 0; k++; j < grandChild.children.length - 1) {
constgrandGrandChild = grandChild.children[j]; result.push(grandGrandChild); }}else{ result.push(grandChild); }}}else{ result.push(child); }}return result;
}
Copy the codeWell, this is already a headache, and it’s just two levels of recursion. Think about how bad it would be to recurse to the third, fourth, and tenth levels.
And this is just some leaves; What if you want to convert the tree to an array and return it? To make matters worse, if you want to use this version of the loop, you must determine the maximum depth you want to support.
Now look at the recursive version:
const getLeaves = tree= > {
if(! tree.children) {If a tree has no children, its leaves are the tree itself.
return tree;
}
return tree.children Otherwise its leaves are the leaves of all its children.
.map(getLeaves) // In this step, we can nest arrays ([grandChild1, [grandChild1, grandChild2],... )
.reduce((acc, item) = > acc.concat(item), []); / / so we use the concat to connect to smooth the array [1, 2, 3]. The concat (4) = > [1, 2, 3, 4] and [1, 2, 3]. The concat ([4]) = > [1, 2, 3, 4]
}
Copy the codeThat’s all, and it works at any level of recursion.
Disadvantages of recursion in JavaScript
Unfortunately, recursive functions have one big drawback: damned out-of-bounds errors.
Uncaught RangeError: Maximum call stack size exceeded
Copy the codeLike many languages, JavaScript keeps track of all function calls in the stack. There is a maximum stack size, beyond which a RangeError will be caused. In a loop nested call, the stack is cleared once the root function completes. But with recursion, the first function call does not end until all other calls have been resolved. So if we call too many, we’re going to get this error.
To solve the stack size problem, you can try to ensure that calculations do not approach the stack size limit. Depending on the platform, the limit seems to be around 10,000. So, we can still use recursion in JavaScript, just be careful.
If you can’t limit the size of recursion, there are two solutions: tail-call optimization and trampoline function optimization.
Tail-call optimization
All languages that rely heavily on recursion use this optimization, such as Haskell. Support for tail-call optimization in JavaScript is implemented in Node.js V6.
A tail-call is when the last statement of a function is a call to another function. The optimization is to have the tail-calling function replace the parent function in the stack. That way, recursive functions don’t add to the stack. Note that for this to work, the recursive call must be the last statement of the recursive function. So the return loop (..) ; Is a valid tail-call optimization, but return loop() + v; It isn’t.
Let’s optimize the summation example with a tail call:
const sum = (array, result = 0) = > {
if(! array.length) {return result;
}
const [first, ...rest] = array;
return sum(rest, first + result);
}
Copy the codeThis allows the runtime engine to avoid call stack errors. Unfortunately, it no longer works in Node.js because support for tail-call optimization was removed in Node 8. Maybe it will in the future, but so far, it doesn’t exist.
Trampoline function optimization
Another solution is called the trampoline function. The idea is to use deferred computation to perform recursive calls later, one recursion at a time. Let’s look at an example:
const sum = (array) = > {
const loop = (array, result = 0) = >() = > {// Instead of executing immediately, the code returns a function to be executed later: it is lazy
if(! array.length) {return result;
}
const [first, ...rest] = array;
return loop(rest, first + result);
};
// When we execute this loop, all we get is a function that performs the first step, so there is no recursion.
let recursion = loop(array);
// As long as we get another function, there are other steps in the recursion
while (typeof recursion === 'function') {
recursion = recursion(); // We perform the current step and then retrieve the next one
}
// Return the result of the last recursion
return recursion;
}
Copy the codeIt works, but there’s a big downside to this approach: it’s slow. For each recursion, a new function is created, and for large recursions, a large number of functions are created. This is very upsetting. Sure, we won’t get an error, but it will slow down (or even freeze) the function.
From recursion to iteration
If you end up with performance or maximum call stack size overruns, you can still convert the recursive version to the iterative version. Unfortunately, as you’ll see, iterative versions are often more complex.
Let’s take the implementation of getLeaves as an example and turn the recursive logic into iteration. I know the result. I’ve tried it before, and it sucks. Now let’s try it again, but this time recursively.
// Recursive version
const getLeaves = tree= > {
if(! tree.children) {If a tree has no children, its leaves are the tree itself.
return tree;
}
return tree.children Otherwise its leaves are the leaves of all its children.
.map(getLeaves) // In this step, we can nest arrays ([grandChild1, [grandChild1, grandChild2],... )
.reduce((acc, item) = > acc.concat(item), []); / / so we use the concat to connect to smooth the array [1, 2, 3]. The concat (4) = > [1, 2, 3, 4] and [1, 2, 3]. The concat ([4]) = > [1, 2, 3, 4]
}
Copy the codeFirst, we need to refactor the recursive function to get the accumulator parameter, which will be used to construct the result. It would be even shorter to write:
const getLeaves = (tree, result = []) = > {
if(! tree.children) {return [...result, tree];
}
return tree.children
.reduce((acc, subTree) = > getLeaves(subTree, acc), result);
}
Copy the codeThen, the trick here is to expand the recursive call onto the stack of remaining calculations. Initializes the result accumulator outside the recursion and pushes the arguments into the recursive function onto the stack. Finally, the stacked operations are unstacked to get the final result:
const getLeaves = tree= > {
const stack = [tree]; // Add the initial tree to the stack
const result = []; // Initialize the result accumulator
while (stack.length) { // As long as there is one item in the stack
const currentTree = stack.pop(); // Get the first item in the stack
if(! currentTree.children) {If a tree has no children, its leaves are the tree itself.
result.unshift(currentTree); // So add it to the result
continue; } stack.push(... currentTree.children);// Otherwise, all children are added to the stack for processing in the next iteration
}
return result;
}
Copy the codeThis seems a bit difficult, so let’s do it again with quickSort. Here’s the recursive version:
const quickSort = array= > {
if (array.length <= 1) {
return array; // An array with one or fewer elements is already sorted
}
const [first, ...rest] = array;
// Then separate all elements larger and smaller than the first element
const smaller = [], bigger = [];
for (var i = 0; i < rest.length; i++) {
const value = rest[i];
if (value < first) { / / small
smaller.push(value);
} else { / / bigbigger.push(value); }}// The sorted array is
return [
...quickSort(smaller), // The sorted array of all elements less than or equal to the first element
first, // The first element. quickSort(bigger),// The sorted array of all elements greater than the first
];
};
Copy the codeconst quickSort = (array, result = []) = > {
if (array.length <= 1) {
return result.concat(array); // An array with one or fewer elements is already sorted
}
const [first, ...rest] = array;
// Then separate all elements larger and smaller than the first element
const smaller = [], bigger = [];
for (var i = 0; i < rest.length; i++) {
const value = rest[i];
if (value < first) { / / small
smaller.push(value);
} else { / / bigbigger.push(value); }}// The sorted array is
return [
...quickSort(smaller, result), // The sorted array of all elements less than or equal to the first element
first, // The first element. quickSort(bigger, result),// The sorted array of all elements greater than the first
];
};
Copy the codeThe stack is then used to store the array for sorting, unstacking it in each loop by applying the previous recursive logic.
const quickSort = (array) = > {
const stack = [array]; // We create an array stack to sort
const sorted = [];
// We traverse the stack until it is empty
while (stack.length) {
const currentArray = stack.pop(); // We take the last array in the stack
if (currentArray.length == 1) { // If there is only one element, we add it to the sort
sorted.push(currentArray[0]);
continue;
}
const [first, ...rest] = currentArray; // Otherwise we take the first element in the array
// Then separate all elements larger and smaller than the first element
const smaller = [], bigger = [];
for (var i = 0; i < rest.length; i++) {
const value = rest[i];
if (value < first) { / / small
smaller.push(value);
} else { / / bigbigger.push(value); }}if (bigger.length) {
stack.push(bigger); // We sort by adding larger elements to the stack
}
stack.push([first]); // We add the first element to the stack, and when it is unheaped, the larger elements will already be sorted
if (smaller.length) {
stack.push(smaller); // Finally, we add smaller elements to the stack to sort}}return sorted;
}
Copy the codeLook! So we have an iterative version of quicksort. But remember, this is just an optimization,
Immature optimization is the root of all evil — Donald Gartner
Therefore, do this only when you need it.
conclusion
I like recursion. It is more declarative than the iterative version, and the code is generally shorter. Recursion can easily implement complex logic. Despite the stack overflow issue, it is fine to use in JavaScript without abusing it. And if necessary, you can refactor the recursive function into an iterative version.
So in spite of its shortcomings, I strongly recommend it to you!
If you like this pattern, look at functional programming languages like Scala or Haskell. They love recursion too!
If you find any mistakes in your translation or other areas that need to be improved, you are welcome to the Nuggets Translation Program to revise and PR your translation, and you can also get the corresponding reward points. The permanent link to this article at the beginning of this article is the MarkDown link to this article on GitHub.
The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. The content covers Android, iOS, front-end, back-end, blockchain, products, design, artificial intelligence and other fields. If you want to see more high-quality translation, please continue to pay attention to the Translation plan of Digging Gold, the official Weibo, Zhihu column.