Tail recursion

Before I get into tail recursion, I will take a step back to refresh how I reached the topic of Tail Recursion.

Coming from the foundation of object oriented paradigms, I wanted to understand the principles of functional programming. Of the many principles, one took my attention that I read multiple times to confirm what I just read.

Looping is evil

Functional programming paradigm is about all about expressions. Looping as imperative action and not an expression. If “looping is evil” then how to “loop”? How to iterate over data-structure?

Enter RECURSION

Recursion. Seriously ! StackOverFlowError ! That’s what struck my head immediately. But then I guessed there could be something special in it and I was thrilled to be ‘technically’ surprised 😉.

Recursion – process of a function calling itself

Application of recursion – the infamous example – factorial, fibonacci series are typical applications. Let us look at an implementation of factorial.

// ref: 1 - recursive implementation
def factorial(n: Int): Int = {
  if (n == 1) 1
  else n * factorial(n -1 )
}

A happy little implementation but only until ‘n’ tends to be a large number – just as large as 5000 is sufficient to brought out the evil – StackOverflowError. StackOverflowError occurred because the implementation used stack – an implicit one, called as ‘call stack’ and it was attempted to fill beyond its limit. Stacks are fixed size and they can run out of space. But what is filling the implicit stack? Take a look at the code. When is the expression evaluated? Only when the termination condition n == 1 is met. Until then the expression is preserved in the stack.

# ref: 2
For f (3) = 
stack[0] -> 3 * f(2)
stack[1] -> 3 * 2 * f(1)
stack[2] -> 3 * 2 * 1

When ‘n’ tends to be a large number, the stack is bound to be filled. Now that the problem is understood, how to use recursion without running into StackOverflowError?

The iterative approach to calculate the recursion does not fail even for a large number that failed with recursion. Below snippet is an imperative implementation of factorial.

// ref: 3 - imperative implementation
def factIt(n: Int) = {
  var f = 1
  var index = 1
  for (index <- 1 to n) {
    f = f * index
  }
  f
}

Why did the recursive function run into an error?

In the recursive implementation ref:1, the implicit call stack was preserved because the last expression had to be evaluated out of the return of the recursive call – referring to n * fact (n-1). The stack element has to be preserved to evaluate the product of fact(n-1) and n. This led to preservation of the stack, there by overflowing the capacity of the stack itself for large values of ‘n’.

From recursion to tail recursion

• A type of recursion -- Other types are direction and indirect recursion
• Recursive function calls itself as the last step in the body.

Tail recursion solves the problem of running into StackOverflowError by not having the expression to be evaluated after the recursive call. Instead, the expression is passed as ‘another’ parameter. Let us go through the tail recursive approach of factorial function.

// ref: 4 - tail recursion
def fact(n: Int) = {
  def helper(n: Int, a: Int): Int = {
    if (n == 1) a
    else helper(n-1, a * n)
  }
  helper(n, 1)
}
println(" factorial of 5000" + fact(5000))

Appears more lines of implementation – but effective enough to handle the large input value with recursion. The key piece of code is else helper(n-1, a * n).

• function ‘helper’ invokes itself and that is the final step.
• function ‘helper’ evaluates expressions (n-1, a * n) before invoking itself.
• Expression a * n is the state that gets carried over. It is called accumulation.

Now with the refactored recursive function, is the stack actually used? Or is the stack still used? Answer: the implicit call stack is still used in tail recursive implementation but the problem of StackOverflowError no longer occurs for large values of ‘n’.

Reason => tail call optimization by compilers

Modern day compilers are optimized for tail calls. When the compiler identifies a function to be tail recursive, it internally optimizes the tail recursive functions to use an iterative approach internally – at least for Scala compiler.

Now, do we replace every recursion by tail recursion? Not necessarily. But being aware of such a technique given that the compiler can perform tail call optimizations is important.

I am glad that this article kept you interested this far. Read about significance of tail recursive function, refer blog .