Understanding Recursion and Stack Frames

Every unfinished recursive call keeps state

A recursive function solves a problem through smaller calls. Each unfinished call may retain parameters, local variables, and a return location in a stack frame. A base case and progress toward it are both necessary.

Copy codefun sumTo(n: Int): Long {
    require(n >= 0)
    return if (n == 0) 0L else n.toLong() + sumTo(n - 1)
}

For sumTo(3), the calls are 3 → 2 → 1 → 0, then results unwind as 0, 1, 3, 6. The addition waits until the recursive call returns, so this is not tail recursion. It takes Θ(n) time and Θ(n) stack space.

Large inputs can overflow the call stack despite the mathematical answer fitting in Long. Recursion depth is a resource, separate from total work.

Exercise

Draw the frames for sumTo(4), then implement an iterative version using constant auxiliary space. Compare answers for small values.

Check: avoid probing maximum recursion depth as an API guarantee; available stack capacity varies across runtimes and configuration.

Further reading: Recursive algorithms