Who said interviews were just about testing knowledge? In some cases, it can be a bit of a learning experience for everyone involved. Case in point, I was asked about what kind of compiler optimization may be made from the following code:

int CountOccurences(LinkedNode const * const head, int const dataToCount, int occurences)
{
	if (head == nullptr)
	{
		return occurences;
	}
	if (head->data == dataToCount)
	{
		++occurences;
	}
	return CountOccurences(head->link, dataToCount, occurences);
}

My initial reaction was that maybe the compiler would attempt to do something to our const vars on the stack, considering they never change in the function. Turns out, there is something more going on here.

In recursion, the function call is that of an accordion typically. If you have a 1,000,000 element linked list and you recurse through it, you will have 1,000,000 stacks. But under certain conditions, this is not actually true. The compiler is smart enough to condense 1,000,000 stacks to just one (1) if the function is tail-recursive.

Now, I’ve had some experience with functional programming and tail-recursion is a pretty significant subject. But when using languages like C++ and Java, even when I use tail-recursion-like logic, it never occurred to me that the compiler would have the ability to reason that the stacks don’t need to be held under the prime condition I’ll demonstrate in a second. Even in functional programming, it never stood out. What I mean is sometimes I considered functions to be tail-recursive but they were not. It has to do with the final call in the function and how it gets handled.

Let’s consider a different scenario. We’re instead counting the number of elements in the list…

int CountList(LinkedNode const * const head)
{
	if (head == nullptr) { return 0; }
	return CountList(head->link) + 1;
}

The magic comes when we’re focusing on return control. In this scenario, the compiler cannot do the tail call elimination optimization because the return depends on the previous stacks. This is not tail end recursion and no optimization is made. Whereas in the first set of code counting the occurrences of a number in the list, it is tail end recursion and that stack and be eliminated.

Now that we’ve discussed what tail recursion is strictly, let’s discuss what the tail call elimination optimization is actually doing.

As I mentioned, if the stack isn’t needed, you can just disregard it. And when this was brought up in my interview, the first thing that came to mind was… “Is this something that only happens under release?” Otherwise, you wouldn’t be able to debug a recursive function which I know I have. This spawned a great discussion and experimentation about examining the dissasembly – the compiler and architecture’s point of view.

Let’s compare the first code snippet (CountOccurences) to the dissasembly in Debug vs Release:

LinkedNode a;
a.data = 5;
LinkedNode b;
b.data = 6;
a.link = &b;
CountOccurences(&a, 5, 0);

Right away, the sheer size difference should jump out at you. But the most significant difference is the return of the two functions. When return occurences; happens – the function will do a jmp in Debug to CountOcurrences+53h. However, in Release, the compiler will simply leave the function and return to the caller. There is no unrolling of the stack, its never kept around. There is no need to remember the previous stacks. The return simply aborts as opposed to going back in the accordion so-to-speak.

Wikipedia has an even better demonstration of the dissasembly with its own example here. The tail call elimination. Functional programming garuntees this optimization while other languages might not. I believe in Python this does not exist because the creator opposes it arguing it is harder to debug. If one is like C++ where debug and release allow this optimization to safely be turned on/off, I personally do not see the issue. Apparently even Javascript has this functionality now with ECMAScript6.