Programmers should know recursion, but do you really know how it works?

  • All About Recursion, PTC, TCO and STC in JavaScript
  • Translator: Fundebug

To ensure readability, free translation rather than literal translation is used in this paper.

Introduction of the recursive

A procedure or function in the introduction to the definition or call their own, directly or indirectly, with a kind of method, it is usually the problem of a large complex layers into a similar to the original problem of smaller problems to solve, the recursion strategy only a small number of procedures can be required to describe the problem solving process of repeatedly calculation, greatly reduces the amount of program code.

Let’s take an example, we can define 5 factorial by multiplying 4 factorial by 4, 4 factorial by 4, and so on.

factorial(5) = factorial(4) * 5
factorial(5) = factorial(3) * 4 * 5
factorial(5) = factorial(2) * 3 * 4 * 5
factorial(5) = factorial(1) * 2 * 3 * 4 * 5
factorial(5) = factorial(0) * 1 * 2 * 3 * 4 * 5
factorial(5) = 1 * 1 * 2 * 3 * 4 * 5
Copy the code

The factorial function can be defined intuitively using Haskell Pattern matching:

factorial n = factorial (n- 1)  * n
factorial 0 = 1
Copy the code

In the recursive example, the factorial function itself is recursively called from the first call of factorial(5) until the value of the argument is 0. Here is an example of an image:

Recursive call stack

To understand the call stack, let’s return to the example of the factorial function.

function factorial(n) {
    if (n === 0) {
        return 1
    }

    return n * factorial(n - 1)}Copy the code

If we pass in argument 3, factorial(2), factorial(1), and factorial(0) will be recursively called, so factorial will be called three more times.

Each function call is pushed into the call stack, which looks like this:

factorial(0) // 0 factorial is 1
factorial(1) // This call depends on factorial(0)
factorial(2) // This call depends on factorial(1)
factorial(3) // The drop depends on factorial(2)
Copy the code

Now we modify the code and insert console.trace() to see the current stack status each time:

function factorial(n) {
    console.trace()
    if (n === 0) {
        return 1
    }

    return n * factorial(n - 1)
}

factorial(3)
Copy the code

Let’s look at what the call stack looks like. The first:

Trace
    at factorial (repl:2:9)
    at repl:1:1 // Ignore the low-level implementation details below
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)
    at emitOne (events.js:101:20)
Copy the code

You will notice that the call stack contains a call to the factorial function, in this case factorial(3). Now, to get more interesting, let’s look at the printed call stack for the second time:

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at repl:1:1 // Ignore the low-level implementation details below
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)
Copy the code

We now have two calls to the factorial function.

The third time:

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
Copy the code

For the fourth time:

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
Copy the code

Imagine that if the value of the parameter passed in is extremely large, the call stack will become so large that it may eventually exceed the cache size of the call stack and crash, causing the program to fail. So how to solve this problem? Use tail recursion.

Tail recursion

Tail recursion is a form of recursion that avoids overrunning the stack by constantly pushing functions onto the stack. Call recursively by setting an accumulation parameter and adding up the current value each time.

Let’s see how we can rewrite our definition of factorial to tail recursion:

function factorial(n, total = 1) {
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}
Copy the code

The steps of factorial(3) are as follows:

factorial(3.1) 
factorial(2.3) 
factorial(1.6) 
factorial(0.6) 
Copy the code

The call stack no longer needs to stack factorial multiple times, because each recursive call does not depend on the value of the previous recursive call. Therefore, the complexity of the space is O (1) instead of 0(n).

Next, the call stack is printed out using the console.trace() function.

function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

factorial(3)
Copy the code

Very surprised to find that there is still a lot of pressing!

// ...
// Here are the last two calls to factorial
Trace
    at factorial (repl:2:9) // 3 times pressing
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at repl:1:1 // Ignore the low-level implementation details below
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
Trace
    at factorial (repl:2:9) // Finally the first call is pushed again
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at repl:1:1 // Ignore the low-level implementation details below
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
Copy the code

Why is that? Under Nodejs, we can start the proper tailcall by turning on strict mode and using — Harmony_tailCalls.

'use strict'

function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

factorial(3)
Copy the code

Use the following command:

node --harmony_tailcalls factorial.js
Copy the code

The call stack information is as follows:

Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions.. js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions.. js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions.. js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions.. js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Copy the code

You’ll notice that instead of pushing each call, there’s just a factorial.

Note: Tail recursion doesn’t necessarily speed up your code; On the contrary, it may slow down. However, tail recursion allows you to use less memory and make your recursive functions safer (if you turn Harmony on).

Why does harmony have to be on for tail recursion?

About Fundebug

Fundebug focuses on JavaScript, wechat applets, wechat mini games, Alipay applets, React Native, Node.js and Java real-time BUG monitoring. Since its official launch on November 11, 2016, Fundebug has handled more than 700 million error events in total, which has been recognized by many well-known users such as Google, 360, Kingsoft, and People’s Net. Welcome free trial!

Copyright statement

Reprint please indicate the author Fundebug and this article addresses: blog.fundebug.com/2017/06/14/…