0
function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

In this example, we see that the result will yield:

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

In such a case, isn't there a new stack every time tailrecsum is called? And isn't tailrecsum(5, 0) waiting for the next tailrecsum to finish, hence not closing that stack yet?

itsmarziparzi
  • 699
  • 7
  • 21
  • 1
    Why do you think a new stack would be created by *anything* running in a single process? A call creates a *stack frame* on the stack. – tripleee Feb 13 '18 at 05:35
  • Does a recursion that is not a tail recursion create multiple _stacks_ or multiple _stack frame_? If the latter, by stack I mean the stack frame. – itsmarziparzi Feb 13 '18 at 06:06
  • The whole point of tail recursion elimination is to optimize this. Yes, a naive implementation will recurse in both cases; in languages with tail recursion elimination, it sees that the result isn't pending on any computation, so it can eliminate the stack frame. – tripleee Feb 13 '18 at 06:09
  • "it sees that the result isn't pending on any computation, so it can eliminate the stack frame." That I don't get. To me, it looks like it is pending which is what i meant by "And isn't tailrecsum(5, 0) waiting for the next tailrecsum to finish, hence not closing that stack yet?" – itsmarziparzi Feb 13 '18 at 06:12
  • No, you are reading this incorrectly. The purpose of the two-argument function call is to pass on the intermediate result so that there is nothing to wait on. – tripleee Feb 13 '18 at 06:13
  • I don't understand how there is nothing to wait. If you call tailrecsum(5,0), that tailrecsum will wait until tailrecsum(4,5) is finished, no? – itsmarziparzi Feb 13 '18 at 06:16
  • No. [The answer you copied this from](https://stackoverflow.com/a/37010/874188) is already explaining this, probably better than I can. The result from `tailrecsum(5,0)` is 5 and then it passes that on as the second argument to `tailrecsum(4,5)` precisely so that there is no pending context for that call to wait on. `tailrecsum(5,0)` is now done and `tailrecsum(4,5)` will deliver the final result. TCO notices that there is nothing to wait for and so effectively doesn't do a full recursion (there is no state to save, so it doesn't). – tripleee Feb 13 '18 at 06:20
  • If you undestand Unix `exec()` maybe that helps here. Instead of `return function()` we can optimize by doing `exec function()` and then that function will return the result to our caller. (We are dealing with functions, not processes, so this is obviously just a metaphor.) – tripleee Feb 13 '18 at 06:22
  • No i get that. But the caller has to wait for result of `return function()`. I guess a better question would be asking how the compiler does the optimization. – itsmarziparzi Feb 13 '18 at 06:28
  • Possible duplicate of https://stackoverflow.com/questions/310974/what-is-tail-call-optimization – tripleee Feb 13 '18 at 06:30
  • I found the answer "But with TCO, it can just say "go back to the beginning, only this time change the parameter values to these new ones." It can do that because nothing after the recursive call refers to those values." – itsmarziparzi Feb 13 '18 at 06:38

0 Answers0