Kotlin Recursion

Importance of Base Case

The base case or the terminal condition is a very important condition in any recursive function. This condition tells the program where it needs to stop the execution. If this condition is not specified, the program will run into an infinite loop. For example, consider the example of calculating the factorial of a number using recursion as discussed above. 

The condition

if(num == 1)
        return num.toLong()

is the base condition in that program. If we remove this condition, the program will loop infinitely. Refer to the blog Kotlin Decision Statements for more understanding about this syntax. 

// Kotlin recursive program without base case
// StackOverflow Error
fun Factorial(num: Int):Long{
    return num*Factorial(num-1)  // no terminate condition
}    

fun main() {
    val num: Int = 6
    println("Factorial of $num is: ${Factorial(num)}")
}

Output:

Exception in thread "main" java.lang.StackOverflowError

Must Read Recursion in Data Structure

Kotlin Tail Recursion

In a traditional recursion call, the recursive call is performed first, after which we take the value returned by the recursive call and calculate the output. Tail recursion also performs the same task as traditional recursion; the only difference lies in the order of execution of these steps. In tail recursion, the calculation part is performed before executing the recursive call. We pass the result of the current step to the next recursive call. In short, the tail recursion must perform the recursive call at the end. 

There are certain benefits associated with using tail recursion. For example, tail recursion stores the stack space for the next recursive call as we do not need to save the current function call in the stack memory primarily because the recursive call is performed at the end of the function. Errors like StackOverFlowError do not occur in the case of tail recursion programs.

Factorial of a number using tail-recursion

In the previous section, we saw how to calculate the factorial of a number using traditional recursion. Now we will modify the same program, and calculate the factorial using the tail recursion strategy. The final output will remain the same, but the efficiency of internal calls increases.

// Kotlin program to calculate factorial of a number using tail recursion
fun Factorial(num: Int, res: Int):Long{
    if(num == 1)
        return res.toLong()
    return Factorial(num-1, res * num)  // tail recursion
}    
 
fun main() {
    val num: Int = 6 // Enter the number
    println("Factorial of $num is ${Factorial(num,1)}")
}

Output:

Factorial of 6 is 720

Deep Recursion

The following syntax is used to define a deep recursive function in Kotlin.

@ExperimentalStdlibApi class DeepRecursiveFunction<T, R>

It defines a deep recursive function that keeps its stack on the heap. It does not use the actual call stack, thus allowing room for performing very deep recursive computations/tasks. The deep recursive function should be used if recursion goes deeper than a thousand calls. The invoke method can be used to initiate a deep recursive function. 

The deep recursive function takes one parameter of type <T> as input and returns the result of type <R>. The callRecursive extension allows deep recursive functions to call each other using a heap for the stack. 

For more details, refer to the official Kotlin documentation here.

Must Read Elvis Operator Kotlin

FAQs

1. Which data structure is used to implement recursion?
   The recursion programming paradigm uses a very commonly known data structure known as a stack. A recursive function maintains a call stack, whenever a program invokes a function it is added to the top of the existing call stack.
    
2. Does Kotlin support tail recursion?
   Yes, Kotlin, like many other modern-day programming languages, supports tail recursion. Tail recursion help make the code faster and eliminates chances of StackOverFlowError. 
    
3. Why is recursion used in the first place?
   Recursion helps in solving problems/puzzles that can be broken down into smaller and repetitive problems. It works very smartly on problems with many possible branches and is too complex to solve via an iterative approach. 

Key Takeaways

Cheers if you reached here!! The purpose of this blog was to introduce you to the concept of recursion in Kotlin. We also discussed a modified version of recursion known as tail recursion. We also saw example programs to calculate factorials of a number using traditional recursion and tail recursion.

Also check out - Rod Cutting Problem

Yet there is never an end to the learning process, so check out our Android Development Course on the Coding Ninjas Website to learn everything you need to know about Android development and how to design the applications of the future. Until then, good luck!!