Tail Recursion Optimization

Recently I came to know about amazing concept of tail recursion optimization. If you are a computer scientist, you must be knowing what recursion is. It is a function calling itself multiple times until certain edge condition is reached. When an edge condition is reached, it returns the result at smallest granular level and then the recursion process as whole combines the result from multiple smaller operations.

A good example of recursion would be computing Factorial of a number or computing Fibonacci series at certain point.

Example of recursive code to calculate Factorial and Fibonacci is as follows.

// Recursive implementation of calculating Fibonacci sequence
func fibonacciRecursive(num: Int) -> Int {
    if num < 3 { return 1 }
    return fibonacciRecursive(num: num - 1) + fibonacciRecursive(num: num - 2)
}

// Recursive implementation of calculatingfactorial of the number
func factorialRecursive(num: Int) -> Int {
    if num < 3 { return num }
    return num * factorialRecursive(num: num - 1)
}

However, having recursion can have serious impact on the code performance in terms of increasing stack size. Let's say you want to compute factorial of number say n. In this case recursion will expand itself until it reaches the stack size of n - 2 before computing the first result and then unwind itself to combine results from individual stack frames. This works well if number is small. However, if number is large enough and language or framework has limited stack space, program can eventually crash with Stack Overflow error.

This is even worse when you are combining the result of smaller operations in the process of computing fibonacci. As you can see, at every level it keeps creating two branches which continues to grow exponentially. If you visualize it for operation of computing fibonacci for number n, it can go till levels 2^n-2 with every level adding exponential number of nodes compared to the previous one.

This is indeed not favorable. If you're smart enough, you can go with iterative approach where it's all goody goody and simply - A world full of sunshine and rainbow. It's straight forward, easy to understand and you won't have to bother about growing stack size for larger input numbers.

// Iterative version of calculating Fibonacci series
func fibonacciIterative(num: Int) -> Int {
    var a = 1
    var b = 0
    var temp = 0
    var inputNumber = num
    while inputNumber > 0 {
        temp = a
        a = a + b
        b = temp
        inputNumber = inputNumber - 1
    }
    return temp
}

// Iterative version of calculating factorial of a number
func factorialIterative(num: Int) -> Int {
    var factorial = 1
    var inputNumber = num
    while inputNumber > 1 {
        factorial = factorial * inputNumber
        inputNumber = inputNumber - 1
    }
    return factorial
}

But is this really fun? Let's do it by another approach where it employs the hybrid approach. Which means it looks like recursive operation to naked eyes, but if compiler is smart enough to recognize and remove the recursion and stack frames, it can easily be transformed into an iterative approach written with recursive form.

I have given references at the bottom of the post. This idea if implemented in the ES6, where implemented correctly ES6 can remove the recursive calls and replace the entire logic with recursive one. However, as I mentioned before your compiler should be smart enough to recognize it.

Not to pick on Swift (Which is beautiful language otherwise!) but I tried it on Swift and looks like compiler still maintains the sequential stack frames for every recursive call made, although that might be completely needless given our smart hybrid implementation

Let's execute our hybrid approach on both the examples mentioned above:

Fibonacci Sequence with Hybrid approach

func fibonacciImproved(value: Int) -> Int {
    return fiboImprovedRecur(value: value, a: 1, b: 0)
}

func fiboImprovedRecur(value: Int, a: Int, b: Int) -> Int {
    if value == 0 {
        return b
    }
    return fiboImprovedRecur(value: value - 1, a: a + b, b: a)
}

As you can see in above example, although we are calling recursive version of the code, in the successive iteration we are passing partial result to the next recursive call so that we don't have to wait until it reaches the root case.

In the above example value b is the temporary result. When the input values reaches to 0, we know that we have final result and return that value. As I mentioned, ES6 has this improvement where it recognizes such scenario and remove the necessity to maintain stack frames for successive calls since we no longer need to save state of multiple recursive calls.

Computing factorial of a number with Hybrid approach

func factorialImproved(num: Int) -> Int {
    return recurImprovedFactorial(num: num, currentValue: 1)
}

func recurImprovedFactorial(num: Int, currentValue: Int) -> Int {
    if num < 2 { return currentValue }
    return recurImprovedFactorial(num: num - 1, currentValue: currentValue * num)
}

Similar to our first example, this example too passes partial result to successive recursive call. As it's evident from above code, we pass currentValue to the next recursive call which has partial value of factorial of a given number.

In the successive iteration we modify the passed number too. When number reaches the end case such as in this case when its values falls below 2, we return the value accumulated so far which is final factorial of the number.

• To summarize, reason it works is that unlike pure recursive method where compiler computes the individual results of operation on separate stack frames and then combines them to form a final result, hybrid approach tends to compute intermediate result and then keeps passing the partial result to the next recursive call. This way we don't have to wait until every smaller result is computed and result is combined

• Unlike regular recursion where given the individual stack frames, it doesn't make much sense about final result unless and until they are combined at the end of operation, for hybrid approach given an instant and the current stack frame, we can see the current result of operation at that particular instant. We can then carry it over and continue the operation elsewhere since we already have the full state of operation in terms of iteration sequence and partial result so far

I understand that this might be little bit confusing post compared to other ones. Feel free to criticize me if I failed to tone down the complexity level. You can also send an email to me or shoot a Tweet (@jayeshkawli) if you have any following questions about Tail Recursion Optimization

Ref:

benignbemine

taylodl