Question on “Tail Call Optimization” Article

Question

I have a question regarding this article.

Between this code

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

and this code

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1) I'm confused about how much this helps. Does the second snippet simply have a tail call that creates less overhead because it calculates what it needs before it calls itself again, or is there something more I'm missing?

As I understand it, the tail call still isn't eliminated, just optimized.

2) And why does there need to be odds and odds1 anyway? It still isn't clear to me either.

Answer 1

I'm confused about how much this helps. Does the second snippet simply have a tail call that creates less overhead because it calculates what it needs before it calls itself again, or is there something more I'm missing?

As I understand it, the tail call still isn't eliminated, just optimized.

If the end of a procedure looks like this:

push args
call foo
return

Then the compiler can optimize that away to just

jump startOfFoo

Eliminating the procedure call entirely.

And why does there need to be odds and odds1 anyway? It still isn't clear to me either.

The "contract" of odds specifies only two arguments - the third argument is just an implementation detail. So you hide that away in an internal method, and present a "wrapper" as the external API.

You could call odds1 something like oddsImpl and it would make it clearer, I think.

Answer 2

The first version isn't tail recursive because after getting the value of odds(n - 1, p - 1) it has to then multiply it by (n / p), the second version moves this into the calculation of the parameters for the odds1 function to make it properly tail recursive.

If you look at the call stack then the first would go like this:

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

whereas the second would be:

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

because you're simply returning the value of the recursive call the compiler can optimize this easily:

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

The reason for having odds and odds1 is simply to supply the initial accumulator value when other code calls this function.

Answer 3

The optimisation of tail recursion is as follows, in the first example since you cannot calculate the result of the multiplication return (n / p) * odds(n - 1, p - 1) until you've called odds(n-1), the interperator has to hold our current position in memory (on the stack), and open a new call to odds.

Recursively, that will happen in the next call as well, and the one after it and so forth. So we have n pending operations by the time we reach the end of our recursion and start returning the valuesand calculating the products.

In the second example, since the return statement executed is simply return odds1(n - 1, p - 1, (n / p) * acc) we can calculate the function arguments, and simply call the odds1(n-1) without holding our current position. this is where the optimisation is, because now i dont have to remember where i am every time i open a new frame on the stack.

Think of it like book references. imagine you open a cookbook and go to a certain recipe, and the ingredients are listed as follows:

1. salt
2. the ingredients on the next page

the next page has

1. pepper
2. the ingredients on the next page

etc. how do you tell what all the ingredients are? you have to remember what you saw on every page!

although the second example is more like the following ingredients list:

1. salt
2. forget this, just use what you see on the next page

the next page has:

1. salt
2. pepper
3. forget this, just use what you see on the next page

etc. by the time you reach the last page (note that the analogy is accurate in that both take the same amount of function calls), you have all the ingredients, without having to "keep in memory" what you saw on every page, because it's all there on the last page!