Tail Recursion! What???

You may have heard of recursion, right? It’s when a function calls itself and possibly passes a new set of parameters. This causes stack frame to be created in the stack for every call. If you do not have a stopping condition, well, it leads you to one of favourite site, yep, you guessed it – StackOverflow

Here is a beaten-to-death example of recursion in JavaScript
function factorial(value) {
  // Check out stackframes
  console.trace();

  if (value < 1)
    return 1;

  // Calls itself, create stackframe
  return value * factorial(value - 1);
}

// Should output 120
console.log(factorial(5));

// Give a large value and goto StackOvrflow
console.log(factorial(100000));

So what it tail recursion? Well, its NOT recursion! Eh?
Some languages can convert a recursive function into a normal function with recursive calls becoming a loop internally. Why do that? Because recursion needs a lot of stack memory and is slower because it has to create a stack frame, call the function and pass parameters.

Umm.. let's take a look at recursion

Here is a process map showing multiple stack frames created for recursion, each containing the same parameter but containing different values in different stack frames.

This is what a recursive functions looks like in the Process Map

Now, not all languages support tailrec, so I am going to use Kotlin for examples. The reason being, Kotlin has a keyword called tailrec which has to be applied to the function signature and if your function is not tail-call, it throws a warning, so we can check if we are writing tailrec recursion properly or not.

Can we do it in JavaScript? Ohh, you missed the bus! Chrome V8 has introduced tailrec in JavaScript but then removed it again.

So let's go
// Functions are 'fun' in Kotlin
fun factorial(value: Int): Int {
    if (value <= 1)
        return 1;

    return value * factorial(value - 1);
}

fun main() {
  println( factorial(5) )
}
Now lets add tailrec to it
// Notice tailrec
fun factorial(value: Int): Int {
    if (value <= 1)
        return 1;

    return value * factorial(value - 1);
}

fun main() {
  println( factorial(5) )
}
Annnnd we get a warning!
Kotlin clearly tells us that this is NOT a tailrace function

So when is a recursive function can be TCO (Tail Call Optimised)?
The rule is very simple, the last line should be a recursive call and not an expression.
e.g.
return value * factorial(value-1)
cannot be a tail rec as the statement in not ONLY function call, like this
return factorial(value-1)

But THAT won’t work, the of result factorial will never get multiplied with value on the way back and final result will alway be 1, right? RIGHT!

So, we will change our strategy and multiply value on our way IN, instead of our way out.

// We pass 2 params
// value -> 5, 4, 3, 2, 1
// level -> 5, 20, 50, 120, 120
fun tailfactorial(value: Int, level: Int = 1): Int {
    if (value <= 1)
        return level;

    // LAST statement is ONLY recursive call
    return tailfactorial(value - 1, level * value)
}

fun main() {
  println( factorial(5) )
}

Well, this seems to print the correct result, but is it automatically a tailrec? Well, some language compiler may automatically convert it (like JavaScript did for a while), but Kotlin expects us to explicitly state that it wants us to do that

Finally!
// We finally got our tailrec working
tailrec fun tailfactorial(value: Int, level: Int = 1): Int {
    if (value <= 1)
        return level;

    return tailfactorial(value - 1, level * value)
}

fun main() {
  println( factorial(5) )
}

But how can we be sure if its really converting into a loop internally?
Well, Kotlin lets you decompile Kotlin code into underlying Java source, so let’s have a look

Non tailrec factorial decompiled!
Pretty much a recursive function
Now tailrec tailfactorial decompiled!
Voila! recursive function converted into a loop!

We can further test it by running the code in debugger and step thru the recursive calls and see that no stack frames are being created for tail recursion.

So, tail recursion is a heavy term for ‘convert recursion internally into a loop’, provided we get it right – The last statement can ONLY be recursive call and NOT an expression

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s