Tail recursion

When we write a recursive function in a way that the recursive function call is the last statement in the function is known as tail recursion.

The beauty of the recursive function is we can write very few lines of code to achieve the solution. But because of the nature of the recursive function, we know it uses a call stack to store its execution state. So a simple solution can reach to space complexity of O(n) as every next recursive call will push its memory to the call stack, but if it was an iterative solution the memory space may take O(1), also it can prevent the code from causing the popular StackOverflowError.

// Recursive solution - Space complexity O(n)
fun sumNumber(number : Int): Int {
	if (number <= 0) {
		return 0;
	}
	return number + sumNumber(number - 1)
}
	
// Iterative solution - Space complexity O(1)
fun sumNumber2(_number : Int): Int {
	var number = _number;
	var total = 0;
	while(number > 0) {
		total += number;
		number--;
	}
	return total;
}
        

Some modern compile like kotlin can convert the tail-recursive function into iterative code at the compile time.

The above recursive function seems a tail recursion, as sumNumber(number - 1) is the last call in the function.

But it's not, because if we break the last line, it will be just like first computing the sumNumber(number - 1) and then summing the result of the method with the number variable.

So we can modify the method like below with an extra parameter.

tailrec fun sum(number : Int, total: Int = 0): Int {
	val totalSum = total + number
	if (number <= 0) {
		return totalSum;
	}
	return sum(number - 1, totalSum)
}
        

Now we can see the modified solution with tailrec keyword at the starting of the method which will eventually convert this pure tail-recursive function into an iterative solution with a while loop by the kotlin compiler.