• 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 code

This 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 code

The 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 code

That’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 code

As 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 code

In 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 code

It’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 code

Simple, 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 code

Suppose 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 code

Let’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 code

Well, 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 code

That’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 code

Like 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 code

This 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 code

It 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 code

First, 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 code

Then, 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 code

This 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 code

const 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 code

The 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 code

Look! 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