Recursion

A High School and College Primer for Computer Science Students

Recursion shows up on every computer science exam, in every data structures course, and in virtually every technical interview — and it confuses students far more than it should. If you've stared at a function that calls itself and had no idea how to trace what it actually does, this guide is for you.

**TLDR: Recursion** covers exactly what you need and nothing extra. You'll learn the two required ingredients of any recursive function (base case and recursive case), how to trace execution step by step using the call stack, and a repeatable recipe for writing your own recursive solutions from scratch. The guide then extends those ideas to binary trees and merge sort — the places where recursion stops being optional and becomes the natural way to think. A dedicated section on common bugs helps you diagnose missing base cases, runaway recursion, and exponential blowup before they cost you points. The book closes by connecting recursion to real applications: file systems, parsers, and AI search.

All examples are written in clean Python-style pseudocode so the logic stays front and center. Whether you're prepping for an AP Computer Science exam, working through a college intro course, or learning recursion for beginners on your own, this primer gets you oriented fast.

Pick it up, read it in one sitting, and walk into your next class or exam knowing exactly what recursion does.

What you'll learn

Define recursion and identify base cases and recursive cases in any recursive function
Trace a recursive call by hand using the call stack
Write recursive solutions for classic problems like factorial, Fibonacci, sum of a list, and reversing a string
Recognize when recursion helps versus when iteration is the better tool
Understand recursion on data structures, including lists, trees, and divide-and-conquer algorithms
Spot and fix common recursion bugs: missing base cases, infinite recursion, and stack overflow

What's inside

1. What Recursion Actually Is

Introduces recursion as a function that calls itself, with the two required ingredients (base case and recursive case) and a first worked example.
2. The Call Stack: How Recursion Runs

Shows what happens in memory when a function calls itself, using stack frames to trace execution step by step.
3. Writing Your Own Recursive Functions

A repeatable recipe for designing recursive solutions, applied to sum-of-list, string reversal, and power functions.
4. Recursion on Structured Data: Trees and Divide-and-Conquer

Extends recursion beyond numbers to data structures, covering binary trees, merge sort, and why some problems are naturally recursive.
5. Common Bugs and When Not to Use Recursion

Diagnoses missing base cases, wrong recursive steps, and exponential blowup; compares recursion to iteration and offers guidelines for choosing.
6. Why Recursion Matters

Connects recursion to real applications in computer science: file systems, parsers, AI search, and how thinking recursively changes problem solving.

Published by Solid State Press

TLDR STUDY GUIDES

Recursion

A High School and College Primer for Computer Science Students

Solid State Press

Recursion

A High School and College Primer for Computer Science Students

Published by Solid State Press.

Part of the TLDR Study Guides series.

Who This Book Is For

If you are a high school student trying to learn recursion for AP Computer Science A or Principles, a college freshman hitting a wall in an intro programming course, or a self-taught coder who keeps skipping the recursion chapter — this book is for you. It also works for tutors who need a clean, fast way to explain how recursion works in a computer science class without wading through a 900-page textbook.

This short programming concepts book for students covers everything you need: how to read and write a recursive function, what a base case does and why it is not optional, how the call stack in recursion builds and unwinds at runtime, and how recursion applies to trees and divide-and-conquer algorithms. Think of it as a recursion and trees programming concept guide compressed into about 15 focused pages — zero filler.

Read straight through once, then work every example actively — pause before the solution and try it yourself. Finish with the practice problems at the end to confirm you have it.

1 What Recursion Actually Is
2 The Call Stack: How Recursion Runs
3 Writing Your Own Recursive Functions
4 Recursion on Structured Data: Trees and Divide-and-Conquer
5 Common Bugs and When Not to Use Recursion
6 Why Recursion Matters

Chapter 1

What Recursion Actually Is

A function can call other functions — that much you already know. Recursion is what happens when a function calls itself. That single idea is both simpler and stranger than it first sounds, and understanding it unlocks a whole style of problem solving.

Here is the minimal possible example, just to make it concrete:

def countdown(n):
    if n == 0:
        print("Done")
    else:
        print(n)
        countdown(n - 1)

countdown(3) prints 3, then calls countdown(2), which prints 2, then calls countdown(1), which prints 1, then calls countdown(0), which prints "Done" and stops. The function keeps handing the problem to a slightly smaller version of itself until the problem is trivial enough to answer directly.

Every working recursive function has exactly two ingredients. Miss either one and the function breaks.

Base case: the condition under which the function stops calling itself and returns a direct answer. In countdown, the base case is n == 0. It requires no further recursion — the answer is just "Done."

Recursive case: the part of the function that calls itself with a simpler or smaller input, moving toward the base case. In countdown, the recursive case is countdown(n - 1). Each call reduces n by one, so the function is guaranteed to eventually reach zero.

A common mistake is to think the base case is optional — just a nice safety check. It is not optional. Without a base case, the function calls itself forever (or until the computer runs out of memory and crashes). The base case is what gives the recursion a floor to land on.

Factorial: the standard first example

Factorial of a non-negative integer $n$, written $n!$, is the product of every integer from 1 up to $n$. So $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. By definition, $0! = 1$.

Notice something: $5! = 5 \times 4!$. And $4! = 4 \times 3!$. In general:

$n! = n \times (n-1)!$

Keep reading

You've read the first half of Chapter 1. The complete book covers 6 chapters in roughly fifteen pages — readable in one sitting.

Coming soon to Amazon