Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 147 ยท Functions

Recursion

Learn recursion in Go - base and recursive cases, factorial, Fibonacci, Towers of Hanoi, permutations, growable goroutine stacks, missing tail-call optimization and memoization.

A function is recursive when it calls itself. That sounds circular, but it is one of the most natural ways to solve problems that contain smaller copies of themselves: a folder holds folders, a sentence holds shorter sentences, a sorting job splits into two smaller sorting jobs. Recursion lets you write the solution for the smallest case and a rule for shrinking everything else toward it.

In this lesson you'll write recursive functions in Go: factorial, Fibonacci, the Towers of Hanoi and permutations. You'll see why every recursion needs a base case, how deep recursion behaves in Go (goroutine stacks grow on demand, which is very different from C), what Go does not do (tail-call optimization) and how memoization rescues slow recursive algorithms. Closures help with local recursive helpers, so Anonymous Functions and Closures is useful background.

Base case and recursive case

Every correct recursive function has two parts:

  1. A base case: an input so small that the answer is known directly, with no further calls.
  2. A recursive case: reduce the problem to a smaller one, call yourself on it, and combine the result.

If a call can never reach the base case, the recursion never stops. The factorial of n (written n!) is n ร— (nโˆ’1) ร— โ€ฆ ร— 1, and 0! is defined as 1:

Go Factorial, the classic

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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

20! is 2432902008176640000, which still fits in a 64-bit int. 21! does not, and the result would silently wrap around (Basic Types explains overflow), so real code would use math/big for bigger factorials.

What happens at runtime

Each call gets its own set of local variables, kept in a stack frame. factorial(3) calls factorial(2), which calls factorial(1); that one hits the base case and returns 1, and then each waiting call finishes its multiplication on the way back. You can watch it with an indented trace:

Go Tracing the 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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

The calls go inward first, then the returns unwind outward. Keeping this picture in mind makes every recursive function easier to reason about.

Several recursive calls: Fibonacci

Fibonacci numbers start 0, 1 and each next number is the sum of the previous two. Its definition translates directly to code, with two base cases:

Go Naive Fibonacci and its cost

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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

The call count explodes: fib(25) needs about a quarter of a million calls to produce a number below 100,000. The reason is repeated work. fib(5) computes fib(3) twice, fib(2) three times and so on, and the waste grows exponentially. We'll fix that with memoization shortly.

Towers of Hanoi

Hanoi is the textbook case where recursion is dramatically simpler than any loop. To move n disks from peg A to peg C using peg B as a helper: move nโˆ’1 disks to B, move the biggest disk to C, then move the nโˆ’1 disks from B to C.

Go 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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

Three disks need 7 moves and ten disks need 1023: in general 2^n โˆ’ 1. Printing is switched off for the long run so the output stays readable; the counter still sees every move.

Permutations and backtracking

Recursion pairs naturally with backtracking: try a choice, recurse to explore what follows, then undo the choice and try the next. This generates every ordering of a slice:

Go All permutations of three letters

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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

build is a function literal that calls itself, so it is declared with var build func(...) first and assigned afterwards (a literal cannot refer to a variable that is not yet declared). Note the copy append([]string(nil), current...): without it every stored permutation would share one backing array and be overwritten later (How Slices Work explains this aliasing).

How deep can you go?

In C, every thread has a fixed stack (often 1 to 8 MB), and deep recursion overflows it quickly. Go is different: each goroutine starts with a tiny stack of a few kilobytes that the runtime grows automatically by moving it to a bigger block when needed. The limit is large: by default 1 GB on 64-bit systems. A recursion a million levels deep is no problem:

Go Recursing a million levels deep

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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

That works because the stack simply grew. Infinite recursion still ends badly, just later: when the stack passes the limit, the runtime aborts with a fatal error that begins runtime: goroutine stack exceeds 1000000000-byte limit and ends with fatal error: stack overflow. Unlike an ordinary panic, you cannot recover from it. We don't run that here, because it would burn a lot of memory before failing.

Go does not perform tail-call optimization. A function whose last action is calling itself still builds one new stack frame per call. If your algorithm can recurse a million times or more, or runs on untrusted input (like a deeply nested JSON document), prefer a loop or an explicit stack.

The loop version of sumTo is simple and uses constant memory:

Go Turning recursion into 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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

Use recursion when the problem is naturally recursive (trees, nested data, divide and conquer, backtracking). Use a loop when the recursion is just repetition.

Memoization

Memoization means remembering results you already computed. For fib, a map from n to its answer removes all the repeated work:

Go 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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

Each value is now computed once, so fib(90) takes 90 steps instead of billions. The map lives inside a closure, hidden from the rest of the program. fib(90) is 2880067194370816120, near the top of the int64 range; fib(92) is the last Fibonacci number that fits. If concurrent goroutines will call the function, the map needs a lock (The sync Package).

Recursion on trees

Recursion shines on nested structures, because the structure's own shape tells you where to recurse. A tiny tree of nodes, each with a name and children:

Go Walking a 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 bufio.Scanner or fmt.Scan), it gets the next line from this box.

The base case is hidden: a node with no children makes the for loop run zero times, so the recursion stops by itself. This is the same idea that filepath.WalkDir uses to visit directories.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does every correct recursive function need?

    Without a base case the function keeps calling itself and never returns normally.
  2. 2. How does Go handle very deep recursion compared with C?

    Goroutine stacks start small and are grown by the runtime. Only runaway recursion that exceeds the limit ends in a fatal stack overflow.
  3. 3. Does Go optimize tail calls?

    The Go compiler does not do tail-call optimization, so a loop is the safer choice for very deep repetition.
  4. 4. Why is naive recursive fib(n) so slow?

    fib(n-1) and fib(n-2) overlap heavily. Memoization stores each result so every value is computed once.
  5. 5. How many moves does Towers of Hanoi need for 4 disks?

    The minimum number of moves is 2^n - 1, so 2^4 - 1 = 15.

Summary

  • A recursive function needs a base case and a recursive case that moves toward it.
  • Each call has its own stack frame; calls go in first, then returns unwind back out.
  • Multiple recursive calls on overlapping subproblems (naive Fibonacci) grow exponentially; memoize with a map, often inside a closure.
  • A function literal that calls itself must be declared first with var f func(...) and then assigned.
  • Backtracking (choose, recurse, undo) generates permutations and combinations; copy slices before storing them.
  • Goroutine stacks grow dynamically up to 1 GB, so deep recursion is fine, but Go has no tail-call optimization and runaway recursion ends in an unrecoverable stack overflow.
  • Prefer loops when the recursion is just repetition, and recursion when the data or problem is itself nested.

Next: Functions as Values and Higher-Order Functions shows how to pass behavior around.