In "traditional" recursion, each recursive call is pushed onto the function call stack. This means that your recursive solution will eventually run out of memory when the number of recursive calls is more than what the function call stack can handle.

e.g., consider the following recursive solution for calculating the sum of all positive integers up to a given `n`:

  fn sum(n):
    if n == 0:
      return 0
    else:
      return n + sum(n - 1)    // A

When n = 1000, your function call stack will have to hold ~1000 calls (fn(1000), fn(999), fn(998), fn(997), and so on...), before it's able to compute the sum. This is because the return statement in line A above, needs to keep track of the variable `n` from the calling function in order to be able to compute the return value. If only there was some way to eliminate that variable `n`...

That's where tail-recursion or tail-call optimization comes in:

  fn sum_tail(n, pre_sum):
    if n == 0:
      return pre_sum
    return sum_tail(n - 1, pre_sum + n)    // B
    
  fn sum(n):
    return sum_tail(n, 0)

In this solution, the return statement at line B does not depend on any variable from the calling function (it simply passes that value on to next function call), and so the calling function can immediately be popped off the stack, saving stack space and making your solution more memory-efficient.

It's useful to know that whether any stack space can actually be saved, depends on whether your language of choice implements tail-call optimization. e.g., JavaScript recently started supporting tail-call optimization after ES6 [1], and Python does not support it [2].

[1] http://2ality.com/2015/06/tail-call-optimization.html [2] https://stackoverflow.com/questions/13591970/does-python-opt...

1.	Twitterpated(worldwidewords.org) 1 points by cdax 6 years ago \| 0 comments
2.	Just realised that MDH uncle’s photo only appears on the vegetarian items(reddit.com) 2 points by cdax 6 years ago \| 0 comments
3.	7 years ago \| discuss
4.	Show HN: Setop – Set operations in the Unix shell(github.com) 6 points by cdax 10 years ago \| 0 comments

user:	cdax
created:	February 14, 2016
karma:	11