Tail Recursion

Kotlin

Function programming — where algebra meets code.

Photo Taken Author

The previous article, the art of recursion, showed that deep levels of recursion can cause stack overflow errors. However, all is not lost. Kotlin allows your recursive algorithms in a tail-recursive style and no longer risk your app crashing from stack overflow errors.

A tail-recursive function is a function whose the last action is a call to itself. When the compiler detects a tail recursive function, it will transform the function into a loop like version. Consequently, the function will require only one stack frame — eliminating the need for additional stack frames.

This sum function from the previous article, is it tail-recursive?

fun sum(nums: List<Int>): Int =
    if (nums.isEmpty()) {
        0
    } else {
        nums[0] + sum(nums.drop(1))
    }

It could tempting to think it is. But it’s not.

When the else block is evaluated, the compiler will find this:

nums[0] + sum(nums.drop(1))

There are three operations:

• Get the first integer in the list, nums[0] .
• Call to the sum function with the remaining integers in the list.
• Add the value returned by the sum function to the first integer in the list.

If you express this in code:

val y = nums[0]
val x = sum(nums.drop(1))
val res = x + y
return result

How could you make the sum function tail recursive?

Kotlin provides a tailrec modifier. If you mark a function with the tailrec modifier and it meets the requirements of a tail recursion, the compiler will optimise the function to a loop like version.

If you try to label the sum function with the tailrec modifier, the IDE will complain because the sum function does not meet the requirements of a tail recursion.

You can make the sum function tail recursive using the following simple steps.

1. Keep the original function signature the same. The sum function signature does not change.
2. Create the second function, call it sumWithAccumulator and make it private. This new function will have the same signature as the original one and with an additional parameter, accumulator: Int . Then mark the function with the tailrec modifier. It’s signature will look like this:

private tailrec fun sumWithAccumulator(
    nums: List<Int>,
    accumulator: Int
): Int = ???

3. Copy the implementation of the original function to this new function. Then modify it to use the accumulator parameter:

private tailrec fun sumWithAccumulator(
    nums: List<Int>,
    accumulator: Int
): Int =
    if (nums.isEmpty()) {
        accumulator
    } else {
        sumWithAccumulator(nums.drop(1), accumulator + nums[1])
    }

A few things things to note:

I marked the function with the tailrec modifier to tell the complier to optimise it. There are no IDE warnings since the function meets the requirements of a tail recursion.

Warning: If you mark a function that does not meet the requirements of a tail recursion with the tailrec modifier, the compiler will not optimise the function and there are possibilities of a stack overflow errors.

The first parameter of the function is the list of integers. The function has the second parameter, the accumulator . When the base case is reached, the function returns the accumulator instead of 0 .

The original sum function passed to itself the remaining integers and added the result later the first integer in the list. This new approach keeps track of the “accumulator” (total sum) with each recursive call. As a result, the last action of thesumWithAccumulator function is a call to itself. Like this:

sumWithAccumulator(nums.drop(1), accumulator + nums[1])

Now, the compiler can optimise the function into a loop like version. And you still have the benefits of functional code. How cool!

4. For the last step, you’ll call sumWithAccumulator function from the sum function passing the list of integers and an identity value as the initial value of theaccumulator . The identity value for sum algorithm is 0. The identity value for product algorthm is 1. The identity value for string concatenation is an empty string.(“”).

fun sum(nums: List<Int>): Int = sumWithAccumulator(nums, 0)

When you maintain the original sum function signature, the other programmers using the function will not have to provide the initial seed value. They’ll will not even know that the algorithm used a seed. (Maybe they shouldn’t know🤪).

Bonus

A tail recursive function to calculate the factorial of an integer:

fun factorial(num: Int): Int = factorialWithAccumulator(num, accumulator = 1)

private tailrec fun factorialWithAccumulator(
    num: Int,
    accumulator: Int
): Int {
    return if (num <= 0) {
        accumulator
    } else {
        factorialWithAccumulator(num - 1, accumulator * (num))
    }
}

Have functional fun! 🥳

Resources:

• Functional programming simplified
• Category Theory