Kotlin Recursion

Recursion happens when a function calls itself. Each call works on a smaller version of the problem until a base condition is met. Recursion is useful for problems that naturally break into smaller identical sub-problems, like factorials, trees, and Fibonacci sequences.

The Two Rules of Recursion

Rule 1: Base Case
  A condition that STOPS the recursion.
  Without it, the function calls itself forever.

Rule 2: Recursive Case
  The function calls itself with a SMALLER or SIMPLER input.
  Every call must move closer to the base case.

Example: Factorial

The factorial of n (written n!) means: n × (n-1) × (n-2) × ... × 1

fun factorial(n: Int): Int {
    if (n == 0) return 1        // base case
    return n * factorial(n - 1) // recursive case
}

fun main() {
    println(factorial(5))   // 120
    println(factorial(6))   // 720
}

How factorial(5) Unwinds

factorial(5)
  = 5 × factorial(4)
        = 4 × factorial(3)
              = 3 × factorial(2)
                    = 2 × factorial(1)
                          = 1 × factorial(0)
                                = 1  ← base case

Now it returns back up:
  factorial(0) = 1
  factorial(1) = 1 × 1 = 1
  factorial(2) = 2 × 1 = 2
  factorial(3) = 3 × 2 = 6
  factorial(4) = 4 × 6 = 24
  factorial(5) = 5 × 24 = 120

Example: Fibonacci Sequence

Each Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13...

fun fibonacci(n: Int): Int {
    if (n <= 1) return n          // base cases: fib(0)=0, fib(1)=1
    return fibonacci(n - 1) + fibonacci(n - 2)
}

fun main() {
    for (i in 0..10) {
        print("${fibonacci(i)} ")
    }
}
// Output: 0 1 1 2 3 5 8 13 21 34 55

Example: Sum of Digits

fun sumDigits(n: Int): Int {
    if (n < 10) return n            // single digit: base case
    return n % 10 + sumDigits(n / 10)
}

fun main() {
    println(sumDigits(1234))  // 1+2+3+4 = 10
    println(sumDigits(9876))  // 9+8+7+6 = 30
}

Stack Overflow Risk

Every recursive call adds a frame to the call stack.
Deep recursion fills the stack → StackOverflowError

fun bad(n: Int): Int = bad(n - 1)  // no base case!
// StackOverflowError after ~10,000 calls

Recursion vs Loop

Problem: Sum numbers 1 to N

Loop approach:
  var total = 0
  for (i in 1..n) total += i

Recursive approach:
  fun sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

Both produce the same result.
Use recursion when the structure is naturally recursive (trees, graphs).
Use loops for simple repetition to avoid stack overflow.

Practical Example: Directory Size

// Simulating a folder tree using recursion
data class Folder(val name: String, val fileSize: Int, val children: List)

fun totalSize(folder: Folder): Int {
    val childrenSize = folder.children.sumOf { totalSize(it) }
    return folder.fileSize + childrenSize
}

fun main() {
    val tree = Folder("root", 100, listOf(
        Folder("docs", 200, listOf(
            Folder("reports", 500, emptyList()),
            Folder("templates", 300, emptyList())
        )),
        Folder("images", 1500, listOf(
            Folder("2024", 800, emptyList())
        ))
    ))

    println("Total size: ${totalSize(tree)} KB")
    // Total size: 3400 KB
}

This recursive approach naturally handles folder trees of any depth without knowing the structure in advance.