Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 146 ยท Functions and Closures

Recursion

Learn recursion in Swift - base case and recursive case, factorial, Fibonacci with memoization, Towers of Hanoi, permutations, tree walking, stack overflow and why tail calls are not guaranteed.

A function is recursive when it calls itself. That sounds like a recipe for an endless loop, and it is, unless every call works on a smaller version of the problem and some smallest version can be answered directly. Recursion is the natural tool when a problem is made of smaller copies of itself: a folder that contains folders, a math expression that contains expressions, a puzzle that you can solve by solving a slightly smaller puzzle.

This lesson builds the idea from the ground up. You will see the two parts every recursive function needs, trace a call step by step, solve classic problems (factorial, Fibonacci, Towers of Hanoi, permutations), walk a tree, and learn what happens when recursion goes too deep. Along the way you will see what Swift does and does not promise about the stack, and when a loop is the better answer. You need functions and a little array knowledge.

The two parts of every recursive function

  1. Base case. An input small enough to answer without calling yourself. This is what stops the recursion.
  2. Recursive case. For larger inputs, reduce the problem to a smaller one, call yourself on it, and use the result.

The classic example is the factorial. 5! = 5 ร— 4 ร— 3 ร— 2 ร— 1, and notice that 5! = 5 ร— 4!. The smaller problem (4!) is the same kind of problem. The base case is 0! = 1.

Swift Factorial, with a trace

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 readLine()), it gets the next line from this box.

Read the output from top to bottom. The calls go down (factorial(4), then factorial(3), ..., factorial(0)) without finishing. Only when the base case returns do the pending calls finish, in reverse order, each multiplying its n by the answer from below. The pending calls wait on the call stack, a region of memory that holds one frame (local variables and a return address) for every function that has been called but has not returned yet.

When you design a recursive function, ask three questions: What is the smallest input I can answer directly? How do I make the input smaller? If the smaller call gave me the right answer, how do I build mine from it? If you can answer those, the code almost writes itself. Trust the smaller call; do not try to trace everything in your head.

More small examples

Many recursive functions are short. Recursion over arrays often uses the pattern "first element plus the rest." Swift's dropFirst() gives the rest without copying the elements (see Slices and Views).

Swift Recursion on numbers, strings and arrays

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 readLine()), it gets the next line from this box.

The last function is worth a pause. Multiplying base by itself exponent times needs 13 steps for 3^13. By squaring the half-power you need only about log2(13) calls. Recursion is not only about elegance: when each call cuts the problem in half, it can be dramatically faster. That is the idea behind binary search and merge sort.

Two recursive calls: the Fibonacci trap

Fibonacci numbers are defined by fib(n) = fib(n-1) + fib(n-2), starting with fib(0) = 0 and fib(1) = 1. The direct translation is beautiful and disastrous at the same time, because the two calls repeat each other's work. Let us count the calls.

Swift Naive Fibonacci counts its own calls

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 readLine()), it gets the next line from this box.

Each time n grows by 5 the number of calls grows roughly eleven-fold. The cost is exponential: fib(40) would need hundreds of millions of calls. The tree of calls recomputes fib(3), fib(2) and so on over and over.

Memoization

The fix is to remember answers you have already computed. This is called memoization: a dictionary maps each n to its result, and each value is computed only once.

Swift Memoized 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 readLine()), it gets the next line from this box.

The nested function fib captures cache and calls, so the state is private to each top-level call, with no global variables needed. The number of calls is now linear in n, and fib(90) is instant. (Int is 64 bits and overflows around fib(93); the arithmetic would trap, as covered in Working with Numbers.) For this particular sequence, a simple loop with two variables is even better, which brings up a general point: use recursion when it makes the logic clearer, not by default.

Branching problems: Hanoi, permutations, subsets

Some problems are naturally recursive and awkward as loops. The Towers of Hanoi asks you to move n disks from one peg to another, one at a time, never placing a larger disk on a smaller one. The insight: to move n disks, move n-1 out of the way, move the biggest, then move the n-1 back on top.

Swift Towers of Hanoi

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 readLine()), it gets the next line from this box.

The number of moves is 2^n - 1, so recursion that makes two calls of size n - 1 doubles the work with each added disk.

Backtracking problems follow a similar pattern: try each choice, solve the rest recursively, collect the results. Here are all permutations and all subsets of a small array.

Swift Permutations and subsets

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 readLine()), it gets the next line from this box.

For each possible first item, the function permutes the remaining items; that is exactly how you would do it by hand. subsets uses the idea "every subset either leaves out the first item or includes it", so it takes the subsets of the rest and adds a copy with the first item put in front. Both grow very fast (5! = 120, 2^10 = 1024), which is a property of the problems, not of recursion.

Recursion on trees

Where recursion truly shines is on data that is itself nested. A folder contains files and other folders; each folder is again a folder. A recursive function mirrors the shape of the data. An enum with the indirect keyword (see Indirect Enums and Recursive Types) lets a type contain itself:

Swift Walking a folder tree

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 readLine()), it gets the next line from this box.

The base case is a file (it contains nothing). The recursive case is a folder: handle each child by calling the same function. Notice there is no explicit loop that tracks "how deep are we?" The depth lives in the call stack. A tree, a JSON document, an expression like (1 + 2) * 3: all follow the same pattern.

When recursion goes wrong

Missing base case

Without a base case, or with a recursive call that does not get closer to it, the function calls itself until the stack is full. Swift can even detect the most obvious cases at compile time:

Swift Infinite recursion (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 readLine()), it gets the next line from this box.

The compiler warns function call causes an infinite recursion but still builds the program, because the code is legal. At run time the stack keeps growing until the system stops the program. On a typical desktop, that is a stack overflow, shown as a segmentation fault, with a default stack of a few megabytes (commonly 8 MB for the main thread on Linux). In this sandbox the run is terminated by the system (signal SIGKILL). Either way, the program does not reach a result, and no catch can recover from it.

A stack overflow is not an error you can catch. Swift has no exception for it. Keep recursion depth under control when the depth depends on user data: a list with a million items, or a deeply nested JSON file that a user controls, can crash a service.

Deep but finite recursion

Even correct recursion can be too deep. Each frame costs perhaps 32 to 200 bytes or more, depending on the function. A recursion depth of 100,000 is usually fine; 10 million is not. Where the limit sits depends on the platform, thread and optimization level, so never rely on an exact number. Background threads often have smaller stacks than the main thread.

Tail calls: do not count on them

A tail call is a recursive call that is the very last thing a function does, with nothing left to do afterwards. In languages such as Scheme, tail calls are guaranteed not to grow the stack. Swift gives no such guarantee. The optimizer may turn a tail-recursive function into a loop (and with -O it often does), but the language does not promise it, and debug builds do not do it at all. Code that only works because of the optimizer is a bug waiting for a different build setting.

Swift Tail recursion versus a loop

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 readLine()), it gets the next line from this box.

Both work here, but only the loop is guaranteed to for any n. When the depth can be large and unpredictable, convert the recursion to a loop with your own stack:

Swift Replacing recursion 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 readLine()), it gets the next line from this box.

The explicit stack lives on the heap and grows as needed, so a deep tree cannot overflow it. You trade a little readability for safety.

Choosing recursion

  • Use it for naturally nested data (trees, expressions, folders), divide-and-conquer algorithms (binary search, merge sort) and backtracking (permutations, puzzles).
  • Avoid it for simple counting or accumulating, where a loop is clearer, and for inputs whose depth you do not control.
  • Watch for repeated work. If a recursive function calls itself twice on overlapping subproblems, add memoization, or turn it into a loop or dynamic programming.
  • Always check the base case first, and make sure each call moves closer to it.

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?

    Without a base case the function never stops; without a recursive case that shrinks the problem, it never makes progress.
  2. 2. Why is the naive recursive Fibonacci so slow?

    fib(n) calls fib(n-1) and fib(n-2), which overlap heavily. The number of calls roughly doubles with each step, which memoization fixes.
  3. 3. What happens when recursion is too deep for the stack?

    A stack overflow ends the process, usually with a segmentation fault. Swift has no catchable error for it.
  4. 4. Does Swift guarantee tail-call optimization?

    The optimizer often turns tail recursion into a loop in -O builds, but it is not part of the language contract, and debug builds keep the frames.
  5. 5. Which problem is the best fit for recursion?

    Nested data has the same shape at every level, so a function that mirrors that shape is the clearest solution. The others are simple loops.

Summary

  • A recursive function calls itself on a smaller problem and needs a base case to stop.
  • Pending calls sit on the call stack; too many cause a stack overflow that cannot be caught.
  • Divide-and-conquer recursion (fast exponentiation, binary search) can be much faster than a loop that does one step at a time.
  • Overlapping subproblems, as in Fibonacci, cost exponential time; memoize with a dictionary or use a loop.
  • Recursion fits trees, nested data and backtracking; use indirect enum for recursive data types.
  • Swift does not guarantee tail-call optimization. For unbounded depth, use a loop or an explicit stack.

Next: Property Wrappers