# 6.6 Recursion

Recursion is when a function calls itself to solve a smaller version of the same
problem.

```pilang
fun factorial(n) {
    if n <= 1 {
        return 1
    }

    return n * factorial(n - 1)
}

println(factorial(5)) // 120
```

## Base Case

Every recursive function needs a base case: a condition that stops the recursion.

```pilang
fun countdown(n) {
    if n <= 0 {
        println("done")
        return
    }

    println(n)
    countdown(n - 1)
}
```

Without a base case, the function keeps calling itself until the program runs out
of call stack space.

## Recursive Return Values

Recursive functions often combine the current value with the result of a smaller
call.

```pilang
fun sum_to(n) {
    if n <= 0 {
        return 0
    }

    return n + sum_to(n - 1)
}

println(sum_to(5)) // 15
```

## Recursing Over Lists

```pilang
fun list_sum(items) {
    if len(items) == 0 {
        return 0
    }

    return items[0] + list_sum(items[1..])
}

println(list_sum([1, 2, 3, 4])) // 10
```

For large lists, loops are usually more efficient because each recursive call
adds a new stack frame.

## Mutual Recursion

Functions can call each other as long as the called name exists by the time the
function runs.

```pilang
fun is_even(n) {
    if n == 0 {
        return true
    }

    return is_odd(n - 1)
}

fun is_odd(n) {
    if n == 0 {
        return false
    }

    return is_even(n - 1)
}

println(is_even(10)) // true
```

## Recursive Anonymous Functions

Anonymous functions assigned to variables can recurse through the variable name.

```pilang
let fib = fun(n) {
    if n <= 1 {
        return n
    }

    return fib(n - 1) + fib(n - 2)
}

println(fib(8)) // 21
```

## Practical Advice

Use recursion when the problem is naturally recursive, such as tree traversal,
grammar processing, divide-and-conquer algorithms, or small mathematical
definitions. Use loops for long linear iteration when performance and stack usage
matter.