You should understand the reversed function separately before concerning yourself with reverseAll -
function reverse(word) {
if (word === "") return ""
return reverse(word.substring(1)) + word.charAt(0)
}
console.log(reverse("hello world"))
Starting with reverse("hello_world") we can easily trace the evaluation. Whenever the input word is non-empty, a new stack frame is opened with the recursive call to the sub-problem reverse(word.substring(1)). The ... + word.charAt(0) portion remains in the calling frame and only resumes after the descendant frame returns -
reverse("hello world") =
reverse("ello world") + "h" =
reverse("llo world") + "e" + "h" =
reverse("lo world") + "l" + "e" + "h" =
reverse("o world") + "l" + "l" + "e" + "h" =
reverse(" world") + "o" + "l" + "l" + "e" + "h" =
reverse("world") + " " + "o" + "l" + "l" + "e" + "h" =
reverse("orld") + "w" + " " + "o" + "l" + "l" + "e" + "h" =
reverse("rld") + "o" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
reverse("ld") + "r" + "o" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
reverse("d") + "l" + "r" + "o" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
reverse("") + "d" + "l" + "r" + "o" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
Here we meet the base case, recursion stops and empty string is returned. Now all of the open stack frames collapse, starting with the deepest frame returning its value to its caller -
"" + "d" + "l" + "r" + "o" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
"d" + "l" + "r" + "o" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
"dl" + "r" + "o" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
"dlr" + "o" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
"dlro" + "w" + " " + "o" + "l" + "l" + "e" + "h" =
"dlrow" + " " + "o" + "l" + "l" + "e" + "h" =
"dlrow " + "o" + "l" + "l" + "e" + "h" =
"dlrow o" + "l" + "l" + "e" + "h" =
"dlrow ol" + "l" + "e" + "h" =
"dlrow oll" + "e" + "h" =
"dlrow olle" + "h" =
And finally we can close the outermost call to reverse and return the result -
"dlrow olleh"
In this program, the stack is used to sequence operations and combine resulting values in the intended order. If the input word was significantly large, you would run into a stack overflow because too many frames would be opened and you essentially break the JavaScript runtime limit for such computations. Memory or heap is only used for all of the intermediate string allocations.
The ever-growing stack in the program above demonstrates a recursive process. This is characteristic of any recursive program that doesn't use a tail call. A tail call is simply the last call in your function, returned directly to its caller -
function reverse(word) {
function loop(r, w) {
if (w == "") return r
return loop(w[0] + r, w.substr(1)) // <- loop is the last called
}
return loop("", word)
}
console.log(reverse("hello world"))
This demonstrates a linear iterative process, so called because the process created by the recursive function stays flat and straight like a line -
reverse("hello world") =
loop("", "hello world") =
loop("h", "ello world") =
loop("eh", "llo world") =
loop("leh", "lo world") =
loop("lleh", "o world") =
loop("olleh", " world") =
loop(" olleh", "world") =
loop("w olleh", "orld") =
loop("ow olleh", "rld") =
loop("row olleh", "ld") =
loop("lrow olleh", "d") =
loop("dlrow olleh", "") =
"dlrow olleh"
Some languages have tail call optimization which means the recursive function like the one above would be safe from the stack overflow problem. The compiler or runtime effectively converts the recursive call into a loop -
function reverse(word) {
function loop(r, w) {
while (true) {
if (w == "") return r
r = w[0] + r
w = w.substr(1)
}
}
return loop("", word)
}
console.log(reverse("hello world"))
Above only 2 frames are used and memory allocations of 3 bindings, word, r and w. Memory allocations to compute + and w.substr(1) are also made and are recaptured by the runtime's automatic garbage collector.
In ECMAScript 6, tail call elimination was added to the specification however it is unsupported in almost every popular runtime and that is unlikely to change. That doesn't mean however we are constrained to writing recursive programs using imperative style while loops. There are various techniques to make recursive programs safe even in JavaScript, even in runtimes that do not support this optimization.
Consider this implementation of reverse using loop and recur -
const reverse = word =>
loop
( (r = "", w = word) =>
w == ""
? r
: recur(w[0] + r, w.substr(1))
)
The non-recursive loop and recur functions are generic and allow us to use them to write most recursive programs that will not cause a stack overflow -
const recur = (...values) =>
({ recur, values })
const loop = run =>
{ let r = run ()
while (r && r.recur === recur)
r = run (...r.values)
return r
}
console.log(reverse("hello world"))
This has a very similar performance profile to the while loop above. Only 2 stack frames and 3 bindings with an small overhead of some immediately garbage-collected values like +, substr and recur -
Expand the snippet below to verify the result in your own browser -
const recur = (...values) =>
({ recur, values })
const loop = run =>
{ let r = run ()
while (r && r.recur === recur)
r = run (...r.values)
return r
}
const reverse = word =>
loop
( (r = "", w = word) =>
w == ""
? r
: recur(w[0] + r, w.substr(1))
)
console.log(reverse("hello world"))
"dlrow olleh"
In fact, any recursive program, tail call or not, can be made stack-safe using various techniques. If this sort of thing sounds interesting to you, see this related Q&A for an in-depth exploration of the topic.
