Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 134 ยท Functions

Recursion and tailrec

Learn recursion in Kotlin - base cases, the call stack, StackOverflowError, tail recursion with the tailrec modifier, accumulators, iterative alternatives and when each approach fits.

A recursive function is a function that calls itself. It is the natural way to describe problems that contain smaller copies of themselves: the factorial of 5 is 5 times the factorial of 4, a folder contains folders, an expression contains sub-expressions. Every recursive function needs two parts: a base case that stops the recursion and a recursive case that moves closer to the base case. Without either one, the function never ends.

Recursion has a price: every call takes space on the call stack, and the stack is limited. A recursion that goes a hundred thousand levels deep can crash the program with a StackOverflowError. Kotlin offers a clean answer to this for one important shape of recursion, tail recursion, with the tailrec modifier. This lesson explains how recursion uses the stack, what makes a call a tail call, what tailrec does to your code, and what to do when tailrec does not apply. It builds on Functions and Local and Nested Functions.

Recursion in practice

The classic first example is the factorial, written as n! = n * (n - 1)! with 0! = 1:

Kotlin Factorial and sum with recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is 120, 2432902008176640000 and 5050. factorial(20) is the largest factorial that fits into a Long; factorial(21) overflows silently (see Working with Numbers). Walk through factorial(3) by hand to see what happens:

TEXT
factorial(3)
  -> 3 * factorial(2)
          -> 2 * factorial(1)
                  -> 1                (base case reached)
          -> 2 * 1 = 2
  -> 3 * 2 = 6

The multiplications happen after the inner calls return. While factorial(1) runs, the three calls factorial(3), factorial(2) and factorial(1) are all still waiting on the stack, each remembering its own n.

Recursion on data that is naturally nested

Recursion shines on tree-shaped data. Here is a function that adds up all numbers in a nested structure, where each element is either a number or a list of more elements:

Kotlin Recursion over nested data

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

You see 15 and 3. The function handles one level and delegates the smaller pieces to itself. An iterative version would need a stack of its own, so recursion is the clear winner here, as long as the nesting is not extremely deep. Trees, file systems, JSON and expression parsers are all in this class; the project lessons use it often.

The call stack and StackOverflowError

Each call stores its parameters, local variables and return address in a stack frame. The JVM gives every thread a fixed stack size (typically 512 KB to 1 MB for the main thread, set by -Xss). Simple frames are small, so you can usually go several thousand to some tens of thousands of levels deep, but not millions.

Kotlin Running out of stack (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The first call prints 500500. The second crashes with Exception in thread "main" java.lang.StackOverflowError, followed by a long list of repeated at MainKt.sumTo(main.kt:1) lines, and the process exits with a non-zero code. Unlike an ordinary exception you cannot recover from a deep stack in any meaningful way, though technically you can catch it:

Kotlin Catching StackOverflowError

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is caught: StackOverflowError and program continues. Catching it is useful in tests and demos, but never a design strategy: your code is in an unknown state after the stack unwinds. The right fix is to change the algorithm.

Tail recursion and tailrec

A call is a tail call when it is the very last thing the function does: nothing is left to do with its result except to return it. n * factorial(n - 1) is not a tail call, because the multiplication happens after the call returns. But we can rewrite the function to carry the work done so far in an extra parameter, usually called the accumulator:

Kotlin tailrec factorial with an accumulator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is 120, 2432902008176640000, 500500 and 50000005000000. The same sumTo that crashed at ten million levels now finishes instantly. When a function is marked tailrec and the recursive call is truly in tail position, the compiler rewrites it as a loop: it reuses the same stack frame, updates the parameters and jumps back to the top. No extra frames are created, so no stack can overflow.

A tail-recursive function has this shape:

  1. The recursive call is the last operation, directly in return f(...) or in the branch of an if/when that returns.
  2. Intermediate results travel in parameters (the accumulator) and not in the pending computation.
  3. The function calls itself, not another function (mutual recursion does not qualify).

Typical tail-recursive functions

Kotlin Greatest common divisor and Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

You get 6, 1, 55, 2880067194370816120, true and false. gcd (Euclid's algorithm) is naturally tail recursive. The naive fib(n - 1) + fib(n - 2) is not, and it is also exponentially slow; the accumulator version carries the two latest numbers along and runs in linear time. Default arguments (acc: Long = 1) hide the accumulator from the caller, which is the usual Kotlin trick to keep the public signature clean.

What the compiler tells you

The compiler checks that tailrec is justified. If the recursive call is not in tail position, you do not get an optimization. The compiler reports a warning, the function stays an ordinary recursive function and still overflows on deep input. Look at this version, which is wrongly marked:

Kotlin tailrec on a function that is not tail recursive

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

It still prints 5050, but the compiler (and your IDE) warns that the recursive call is not a tail call (the n + happens after it returns), so no optimization is done. Treat that warning as an error in your head: it means the keyword does nothing. A related rule: tailrec cannot be used on open functions or inside try blocks, because the call is then not the last action.

When tailrec is not enough

Many recursions cannot be made tail recursive without effort. Tree traversal with two branches, quicksort, a depth-first search and the Ackermann function all call themselves more than once. You have three options.

1. Rewrite as a loop. Often the plain loop is the clearest solution:

Kotlin Iterative alternatives

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is 50000005000000, 2432902008176640000 and 50000005000000. For linear recursion over a number or a list, a loop, fold or a standard function (sum, reduce) is almost always shorter than a hand-written recursion.

2. Use your own stack. For tree or graph walks that can be deep, keep an explicit ArrayDeque of work to do instead of using the call stack:

Kotlin Depth-first search with an explicit stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

This prints 100000 and 10. The depth is limited by heap memory instead of the thread stack, which is much larger.

3. Run on a thread with a bigger stack. As a last resort, create a thread with an explicit stack size. Use it sparingly; the real fix is usually one of the two options above.

Kotlin A thread with a bigger stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is 200000. The fourth constructor argument is the requested stack size in bytes. The JVM treats it as a hint, so do not depend on it for portable code.

Design notes

  • Think base case first. Write the stopping condition before the recursive call. A missing or unreachable base case is the number one cause of StackOverflowError.
  • Check progress. Every recursive call must move toward the base case (smaller n, shorter list, deeper in the tree).
  • Prefer iteration for linear problems. If each call makes exactly one recursive call, a loop or tailrec is better.
  • Prefer recursion for branching problems. Trees and divide-and-conquer fit recursion; just keep the depth modest or the tree balanced.
  • Memoize repeated work. Naive double recursion such as fib(n-1) + fib(n-2) recomputes values exponentially often; cache results in a map, or use the accumulator version above.
  • Reading recursion: assume the recursive call works for the smaller input, and only check that the current level combines the answer correctly.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the two essential parts of a recursive function?

    The base case stops the recursion, and every recursive call must get closer to it, or the function never ends.
  2. 2. Why is n * factorial(n - 1) not a tail call?

    A tail call must be the last action. Here the result of the call is used in a multiplication afterwards, so the frame must stay on the stack.
  3. 3. What does the tailrec modifier do for a valid tail-recursive function?

    The compiler turns the self-call into a jump, updating the parameters in place, so the stack does not grow.
  4. 4. Which exception does an infinitely deep recursion eventually cause on the JVM?

    Each call needs a stack frame; when the thread's stack is full, the JVM throws StackOverflowError.
  5. 5. What is a good way to walk a very deep tree without tailrec?

    An explicit stack lives on the heap, which is far larger than the thread stack, so the depth is no longer a problem.

Summary

  • A recursive function needs a base case and a recursive case that approaches it.
  • Each call uses a stack frame; very deep recursion throws StackOverflowError.
  • A tail call is the last action in the function. Move pending work into an accumulator parameter to make recursion tail recursive.
  • tailrec turns valid tail recursion into a loop; if the call is not in tail position, you get a warning and no optimization.
  • For branching or very deep recursion, use loops, fold, an explicit stack, or as a last resort a thread with a larger stack.
  • Memoize or restructure when a recursion repeats work.

Next: Function Types and Type Aliases