Recursion in Kotlin

Introduction

A function that invokes itself is referred to as a recursive function in kotlin, and this approach is termed recursion.

Within the given program, two categories of function calls exist:

• Regular function calls
• Recursive function calls

When the printHello() function is called from the main() function, it's considered a standard function call. However, when the printHello() function is called from within another instance of itself, it qualifies as a recursive function call. This is due to the fact that the printHello() function is calling upon its own definition.

How does recursion in kotlin work in?

Visual Explanation:

Here, the recursive call continues forever causing infinite recursion.

To avoid infinite recursion in kotlin, if...else (or similar approach) can be used where one branch makes the recursive call and other doesn't this leads us to,

Recursion Function Examples

Let us take a look at few examples to understand the concept of recursion better.

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Example 1: Find the Factorial of a Number Using General Recursion

Output:

Visual explanation:

Steps:

factorial(4)              // 1st function call. Argument: 4
4*factorial(3)            // 2nd function call. Argument: 3
4*(3*factorial(2))        // 3rd function call. Argument: 2
4*(3*(2*factorial(1)))    // 4th function call. Argument: 1 
4*(3*(2*1))                 
24

Example 2: Find the Factorial of a Number Using Tail Recursion

The example to compute factorial of a number in the above example cannot be optimized for tail recursion.

Here's a different program to perform the same task.

Code:

Output:

Explanation: The compiler can optimize the recursion in this program as the recursive function is eligible for tail recursion, and we have used tailrec modifier that tells compiler to optimize the recursion. tailrec is a Kotlin keyword that indicates that this function is tail-recursive. Tail recursion is a special form of recursion where the recursive call is the last operation performed in the function. This allows the Kotlin compiler to optimize the recursion into an iterative loop, avoiding stack overflow errors for large inputs.

The code as a whole calculates the factorial of the number 5 and prints the result, which is 120 (5 factorial).

Example 3: Find the Sum of Elements of an Array Using Recursion

Code:

Output:

Explanation: Here, we have initialized an array and passed as an argument to the sum() function. In each recursive call the index value decrement by one. If the index equal to zero or less than then terminate it and return the sum of all the elements.

Tail Recursion

Tail recursion is a universal concept that isn't exclusive to the Kotlin language. Several programming languages, Kotlin included, leverage tail recursion to enhance the efficiency of recursive calls. However, there are languages like Python that lack support for tail recursion.

a. General vs Tail Recursion

In regular recursion, you initiate all the recursive calls beforehand and derive the final result from the returned values afterward. Consequently, the result is not available until all recursive calls are executed.

Utilizing tail recursion offers specific advantages. For instance, tail recursion conserves stack space for subsequent recursive calls. This is possible because there's no requirement to retain the current function call in the stack memory, primarily due to the fact that the recursive call takes place at the conclusion of the function. In the context of tail recursion programs, issues such as StackOverflowError are averted.

Condition for tail recursion A recursive function qualifies as having tail recursion when its self-invoking function call is the final operation it undertakes.

Let's see some examples,

Example 1: Ineligible for tail recursion due to the fact that the function call to itself, n * factorial(n-1), does not constitute the final operation.

Example 2: Qualified for tail recursion as the function's self-invoking call, fibonacci(n-1, a+b, a), stands as the concluding operation.

In Kotlin, to instruct the compiler to execute tail recursion, it's necessary to annotate the function with the tailrec modifier.

Advantages and Disadvantages of Recursion in Kotlin

Advantages:

1. Enhanced code readability and maintainability: Recursive functions frequently lead to more succinct and comprehensible code, particularly when tackling intricate issues.
2. Simple algorithm implementation: Numerous algorithms, like the Tower of Hanoi, lend themselves to straightforward implementation through recursion.
3. Promotes reusability: Recursive functions are often reusable for comparable problems, curtailing the necessity of crafting new code.
4. Adaptability to dynamic data structures: Recursive algorithms can harmonize effectively with dynamic data structures that expand or contract during runtime, showcasing an ability to adjust to structural changes.

Disadvantages:

• Elevated memory consumption: Each recursive call introduces a fresh function entry to the call stack, potentially triggering stack overflow issues when managing substantial datasets.
• Performance implications: Recursive algorithms frequently exhibit inferior performance compared to their iterative counterparts, demanding more memory and CPU cycles.
• Constraints of Tail Recursion Optimization: While Kotlin integrates tail call optimization, a mechanism mitigating certain tail-recursive call overheads, this optimization might not be universally applicable to all recursive functions.
• Complex debugging process: Debugging recursive functions can pose considerable difficulties. Missteps in implementation can lead to predicaments such as endless recursion or flawed base cases, resulting in intricate debugging challenges.