Kotlin Tutoial

Basics

Control Flow

Array & String

Functions

Collections

OOPs Concept

Exception Handling

Null Safety

Regex & Ranges

Java Interoperability

Miscellaneous

Android

Kotlin Recursion

Recursion is a powerful programming technique where a function calls itself in order to break down complex problems into smaller, more manageable parts. Kotlin, like many other programming languages, supports recursive functions. In this tutorial, we'll explore how to use recursion in Kotlin.

1. Basics of Recursion

A recursive function consists of two main parts:

Base Case(s): Condition(s) under which the function will stop calling itself.
Recursive Case(s): Condition(s) under which the function calls itself, usually with a subset or modified version of the original problem.

2. Simple Recursive Example: Factorial

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It's defined as:

0!=1
n!=n×(n−1)!

Using recursion in Kotlin:

fun factorial(n: Int): Long {
    // Base case
    if (n == 0) return 1

    // Recursive case
    return n * factorial(n - 1)
}

fun main() {
    println(factorial(5))  // Outputs: 120
}

3. Handling Recursion Limits

Every recursive function consumes some memory for each call. This is because the function's state (local variables, parameters, return address, etc.) needs to be stored in the call stack. If recursion is too deep, it may lead to a StackOverflowError.

One way to mitigate this is using tail recursion.

4. Tail Recursion

Tail recursion is a special form of recursion where the recursive call is the last operation in the function. The Kotlin compiler optimizes tail-recursive functions to use a loop internally instead of recursive calls, thus preventing stack overflow errors for large inputs.

To define a tail-recursive function in Kotlin, use the tailrec modifier:

tailrec fun factorialTailRecursive(n: Int, accumulator: Long = 1): Long {
    // Base case
    if (n == 0) return accumulator

    // Recursive case
    return factorialTailRecursive(n - 1, n * accumulator)
}

fun main() {
    println(factorialTailRecursive(5))  // Outputs: 120
}

Notice the additional accumulator parameter that keeps the intermediate result. This transformation is common in tail-recursive algorithms.

5. Example: Fibonacci Sequence

The Fibonacci sequence starts with two numbers 0 and 1. Each subsequent number is the sum of the two preceding ones.

Using recursion in Kotlin:

fun fibonacci(n: Int): Int {
    // Base cases
    if (n == 0) return 0
    if (n == 1) return 1

    // Recursive cases
    return fibonacci(n - 1) + fibonacci(n - 2)
}

fun main() {
    println(fibonacci(5))  // Outputs: 5
}

However, the above approach is inefficient for larger values of n due to repetitive calculations. Using tail recursion or memoization can make it more efficient.

Summary

Recursion in Kotlin allows for elegant solutions to problems by breaking them down into simpler sub-problems. While it's a powerful technique, care should be taken with deep recursion to avoid stack overflows. Leveraging tail recursion can optimize many recursive problems, making them both elegant and efficient.

Base case in recursive functions in Kotlin:
- Define a condition that stops the recursion.
```
fun factorial(n: Int): Int {
    return if (n == 0) 1 else n * factorial(n - 1)
}
```

Recursion vs iteration in Kotlin:

Compare recursive and iterative solutions for a task.

// Recursive factorial
fun factorialRecursive(n: Int): Int = if (n == 0) 1 else n * factorialRecursive(n - 1)

// Iterative factorial
fun factorialIterative(n: Int): Int {
    var result = 1
    for (i in 1..n) {
        result *= i
    }
    return result
}

Mutual recursion in Kotlin:

Create functions that call each other in a cycle.

fun isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
fun isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)

Tail recursion in Kotlin:

Optimize recursion to avoid stack overflow.

tailrec fun factorialTailRecursive(n: Int, acc: Int = 1): Int =
    if (n == 0) acc else factorialTailRecursive(n - 1, n * acc)

Using recursion with data structures in Kotlin:

Apply recursion to traverse or manipulate data structures.

data class TreeNode(val value: Int, val left: TreeNode? = null, val right: TreeNode? = null)

fun sumTree(tree: TreeNode?): Int =
    tree?.value ?: 0 + sumTree(tree?.left) + sumTree(tree?.right)

Recursion and functional programming in Kotlin:

Leverage recursion for functional programming principles.

fun <T> List<T>.customMap(transform: (T) -> T): List<T> =
    if (isEmpty()) emptyList() else listOf(transform(first())) + drop(1).customMap(transform)

Recursion and pattern matching in Kotlin:

Use recursion with pattern matching for concise code.

sealed class Tree
data class Leaf(val value: Int) : Tree()
data class Node(val left: Tree, val right: Tree) : Tree()

fun sumTree(tree: Tree): Int = when (tree) {
    is Leaf -> tree.value
    is Node -> sumTree(tree.left) + sumTree(tree.right)
}

Handling large problems with recursion in Kotlin:
- Break down large problems into smaller, more manageable sub-problems.
```
fun fibonacci(n: Int): Int =
    if (n <= 1) n else fibonacci(n - 1) + fibonacci(n - 2)
```

Memory considerations in recursive functions in Kotlin:

Be mindful of memory usage, especially for deep recursive calls.

fun factorial(n: Int, acc: BigInt = 1.toBigInt()): BigInt =
    if (n == 0) acc else factorial(n - 1, n.toBigInt() * acc)

Recursive algorithms in Kotlin:

Implement common algorithms using recursion.

fun binarySearch(arr: List<Int>, target: Int, start: Int = 0, end: Int = arr.size - 1): Int {
    // Implementation
}

Common pitfalls with recursion in Kotlin:

Beware of infinite recursion and excessive memory usage.

fun infiniteRecursion() {
    infiniteRecursion() // This is a common pitfall, leading to a stack overflow.
}