Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 9-12

Recursion

A technique where a function calls itself to solve progressively smaller instances of the same problem.


Quick Answer

A technique where a function calls itself to solve progressively smaller instances of the same problem. Every recursive function needs a base case, an input small enough to answer directly, and a recursive case that passes a smaller version of the problem to the same function and builds on its answer. Use recursion when a problem contains smaller copies of itself: folders inside folders, n!=n×(n−1)!, or a list you can split in half and handle each half the same way.

Why This Matters

Some problems are awkward with loops but short with recursion: listing every file in nested folders, exploring a maze, drawing a fractal, sorting a list by sorting its halves. Recursion lets you solve one level and trust the same code to handle the rest. Get the base case wrong and the calls never stop; the program crashes with a stack overflow.

Intuitive Explanation

Take factorial: 4!=4×3×2×1=24. Notice that 4!=4×3! and 3!=3×2!: each factorial is one multiplication away from a smaller factorial. So a function fact(n) can return n × fact(n − 1), as long as something stops the chain: fact(1) returns 1 without calling anything. That stopping input is the base case; the line that calls fact on a smaller number is the recursive case.

When fact(4) runs, it cannot finish until fact(3) does, which waits for fact(2), which waits for fact(1). The computer keeps each unfinished call on the call stack, a pile of paused calls, each with its own value of n. fact(1) returns 1, then the pile unwinds: fact(2) = 2 × 1 = 2, fact(3) = 3 × 2 = 6, fact(4) = 4 × 6 = 24. Every paused call uses memory, which is why a recursion that never reaches its base case eventually fills the stack and crashes.

A function that calls a different function is not recursion, and neither is a loop. A loop can multiply 1 × 2 × 3 × 4 into a running product and get the same 24 with no self-call and no pile of paused calls. Recursion earns its place when the data is itself nested, like a folder that contains folders, because then the shape of the code matches the shape of the data.

Think of it like this. Looking up a word can be recursive: if the definition uses a word you do not know, you look that word up first, then come back to where you were. You stop at a definition made only of words you know, the base case. A dictionary that defines 'big' as 'large' and 'large' as 'big' is infinite recursion: the lookups never end.

Core idea. Every recursion needs a base case (when to stop) and a recursive case (how to continue).


When to Use

Reach for recursion when a problem contains a smaller copy of itself: a folder holding folders, a family tree, n! defined from (n−1)!, a list you can split and solve half by half. Ask what the smallest case is and how the answer for a smaller input builds the full one. If the job is just repeating a step a known number of times, a loop (Iteration) is simpler and uses less memory. If you split into parts and then combine their answers, you are using Divide and Conquer, usually written recursively.

Tip. Ask: Does a function call itself on a smaller input, with a base case that stops the calls?

How to Recognize It

Before choosing recursion, test whether the problem contains a smaller copy of itself and has a case simple enough to answer outright.

  1. Can the answer for size n be built from the answer to the same problem at a smaller size?

    Yes, as with n!=n×(n−1)!, recursion fits. No, because the work is the same step applied to each item in turn, points to Iteration.

  2. Is there a smallest case you can answer directly, without any further calls?

    Yes gives you the base case. No means a recursive version will never stop, so it cannot be correct as written.

  3. Does every call move strictly closer to that base case?

    Yes means the recursion terminates. If any call passes the same or a larger input, it runs until the call stack overflows.

  4. Does the problem split into two or more smaller copies whose answers are then combined?

    Yes points to Divide and Conquer, a strategy usually written with recursion, as in merge sort. One smaller copy per call is plain recursion.

Recursion vs Iteration vs Divide and Conquer vs Function (Programming)

Recursion repeats work and is built from functions, so it overlaps with loops and with function calls in general. Ask what produces the repetition: a function calling itself, a loop, or a split into several smaller copies.

Recursion

Meaning
Recursion solves a problem by having a function call itself on a smaller input until it reaches a base case.
Key test
The function's own name appears in its body, called on a smaller input.
Formula
f(n)=g(n,f(n−1)), f(n0)=c
Example
fact(n) returns 1 if n is 0, else n * fact(n - 1), so fact(4) is 24.

Iteration

Meaning
Iteration repeats a block with a loop, updating a variable on each pass until a condition fails.
Key test
A for or while loop does the repeating, with no self-calls.
Formula
WHILE B DO S
Example
total = 1, then for i in 1 to 4: total = total * i, which gives 24.

Divide and Conquer

Meaning
Divide and conquer splits a problem into several smaller problems of the same kind, solves each one, and combines the answers.
Key test
Two or more smaller copies per step, then a combining step.
Formula
T(n)=aT(n/b)+f(n)
Example
Merge sort sorts each half of a list, then merges the two sorted halves.

Function (Programming)

Meaning
A function is any named, reusable block of code, and only some functions call themselves.
Key test
Calling a different function is not recursion; only a self-call is.
Example
draw_house() calling draw_roof() is an ordinary call, not recursion.

Formula & Notation

Worked Examples

Example 1 — Trace calls down and results up

Easy

Trace this function for power(3, 4): power(b, e): if e == 0, return 1; otherwise return b × power(b, e − 1). How many calls are made, and what is returned?
Show the steps and the answer
  1. Find the base case: e == 0 returns 1 with no further call.

    Every chain of calls has to end somewhere; here it ends when the exponent reaches 0, since 30=1.

  2. Follow the calls down: power(3, 4) → power(3, 3) → power(3, 2) → power(3, 1) → power(3, 0).

    Each call lowers e by 1, so the input moves steadily toward the base case and the chain must stop.

  3. Return back up: power(3, 0) = 1, power(3, 1) = 3 × 1 = 3, power(3, 2) = 3 × 3 = 9, power(3, 3) = 3 × 9 = 27, power(3, 4) = 3 × 27 = 81.

    No multiplication happens on the way down; each paused call finishes only after the call below it returns.

  4. Count the calls: e took the values 4, 3, 2, 1 and 0, so 5 calls.

    With exponent e the function runs e + 1 times, once for each value down to 0.

Answer: power(3, 4) returns 81 after 5 calls.

Takeaway: Trace recursion in two passes: calls going down to the base case, then results coming back up.

Example 2 — Correct but wasteful: two calls per step

Standard

fib(n): if n < 2, return n; otherwise return fib(n − 1) + fib(n − 2). It correctly gives fib(5) = 5. How many calls does fib(5) make, and how does that compare with a loop that keeps adding the last two numbers?
Show the steps and the answer
  1. Draw the call tree: fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2); each fib(3) calls fib(2) and fib(1); each fib(2) calls fib(1) and fib(0).

    Each call that is not a base case makes two more, so the calls branch like a tree instead of forming one chain.

  2. Count from the bottom: fib(0) and fib(1) are 1 call each; fib(2) is 1 + 1 + 1 = 3; fib(3) is 1 + 3 + 1 = 5; fib(4) is 1 + 5 + 3 = 9; fib(5) is 1 + 9 + 5 = 15.

    A call's total is itself plus the totals of the two calls it makes.

  3. Spot the repeats: fib(3) is computed 2 times and fib(2) 3 times.

    The two branches recompute the same smaller answers without sharing them, which is where the waste comes from.

  4. Compare a loop: start with 0 and 1, then add the last two numbers 4 times to get 1, 2, 3, 5.

    The loop computes each Fibonacci number once: 4 additions where the recursion made 15 calls.

  5. Scale up: fib(30) makes 2,692,537 calls, while the loop does 29 additions.

    The call count grows about 1.6 times for each step up in n, so this recursion is correct but far too slow for large n.

Answer: fib(5) makes 15 calls (fib(3) twice, fib(2) three times), while a loop needs 4 additions. The recursion is correct but wasteful.

Takeaway: When the smaller problems overlap, plain recursion repeats work. Store the answers or use a loop.

Example 3 — Find the mistake: a base case that can be skipped

Application

countdown(n): if n == 0, print 'Liftoff' and stop; otherwise print n, then call countdown(n − 2). Mia tests countdown(6) and it works. She writes: "It has a base case, so it will always stop." Then countdown(5) crashes with a stack overflow. Find the mistake and correct it.
Show the steps and the answer
  1. Trace countdown(6): it prints 6, 4, 2, then n = 0 hits the base case and prints Liftoff.

    This is why Mia's test passed: from an even start, subtracting 2 lands exactly on 0.

  2. Trace countdown(5): it prints 5, 3, 1, then calls countdown(−1), countdown(−3), and so on.

    n skips over 0, and the base case only checks n == 0, so it is never true again.

  3. Explain the crash: each call waits for the next one, and the pile of paused calls grows until the stack runs out of space.

    Having a base case is not enough. Every possible input has to reach it.

  4. Change the base case to: if n <= 0, print 'Liftoff' and stop.

    Now any starting number, odd or even, eventually makes n zero or negative, and the calls end.

  5. Re-trace countdown(5): 5, 3, 1, then n = −1 satisfies n <= 0, so it prints Liftoff.

    The input that crashed now finishes after 4 calls.

Answer: Use the base case n <= 0. countdown(5) then prints 5, 3, 1, Liftoff.

Takeaway: Check that every input reaches the base case, not only the one you tested. A step of −2 can jump over n == 0 but not over n <= 0.

Where You'll See It

  • Russian nesting dolls

    To count the dolls, open one and count the dolls inside (a smaller version of the same job) until you reach the solid innermost doll, the base case that stops the process.

  • Two mirrors facing each other

    Each mirror shows a slightly smaller copy of the reflection inside it, like a recursive call producing a smaller version of the same image, that in principle would go forever without a stopping point.

  • Asking 'how many people are ahead of me in line?'

    You ask the person in front, who asks the person in front of them, down to the very first person who answers '0' (the base case); each answer adds one as it comes back, exactly like a recursive count.

Common Mistakes

  1. The slip: A recursive function doesn't really need a base case if the logic is right.

    Why it's tempting: The recursive case looks like it 'keeps solving', so it seems self-sufficient.

    Instead: Every recursion needs a base case that returns without recursing. Without one, calls never stop and you get infinite recursion and a stack overflow.

  2. The slip: Each recursive call can work on the same-size (or a bigger) problem.

    Why it's tempting: The code compiles and 'calls itself', which feels like progress.

    Instead: The recursive case must move strictly toward the base case (a smaller input). If the problem never shrinks, the base case is never reached and the recursion never ends.

  3. The slip: To understand recursion I must mentally trace every level of calls.

    Why it's tempting: Tracing each step is how we usually check loops, so it feels necessary.

    Instead: Use the recursive leap of faith: assume the recursive call correctly solves the smaller problem, then check only the base case and one combining step.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. `def fact(n): return 1 if n == 0 else n * fact(n - 1)`. What is `fact(4)`, and how many calls are made in total?

    Hint: List the calls until you reach the base case, then multiply back up.

  2. `def total(lst): return 0 if lst == [] else lst[0] + total(lst[1:])`. Trace `total([5, 2, 8])`.

    Hint: Each call takes off the first item and passes on the rest.

  3. `def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2)`. Find `fib(6)`.

    Hint: Build up from `fib(0)` and `fib(1)` instead of tracing every call.

  4. `count_down(n)`: if `n == 0`, print "Go"; otherwise print `n` and call `count_down(n - 1)`. What does `count_down(3)` print?

    Hint: Each call prints before it makes the next call.

  5. A function finds a folder's size by adding its files' sizes and then calling itself on each folder inside it. Is this iteration or recursion?

    Hint: Is a folder inside a folder the same kind of problem?

  6. `def sum_to(n): return n + sum_to(n - 1)`. Calling `sum_to(3)` crashes with a stack overflow. Fix it.

    Hint: What should happen when `n` reaches 0?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Is recursion faster or slower than a loop?

Usually a little slower and hungrier for memory, because every call keeps its own frame on the call stack until it returns. A loop that counts to a million uses one frame; a recursive count to a million needs a million frames, and Python refuses to go deeper than about 1,000 by default. Recursion earns its place when it makes the code much clearer, as with trees and nested folders.

Why is the obvious recursive Fibonacci function so slow?

The direct version, fib(n) = fib(n - 1) + fib(n - 2), makes two calls each time, and those calls repeat the same work: fib(30) calls fib(2) more than 500,000 times. The number of calls grows roughly like 1.6n1.6^n. Storing each answer the first time you work it out, called memoization, means each value is computed once, so the work grows only in proportion to n.

Can every recursive function be rewritten as a loop?

Yes. Any recursion can be turned into a loop, though sometimes you must keep your own stack of pending work to do it, which is what the computer was doing for you. Simple cases, where the self-call is the last thing the function does, become a plain loop easily. The reverse also holds: any loop can be written as a recursion.

Does recursion show up in maths too?

Yes, as recursive definitions and proof by induction. A sequence such as a1=2a_1 = 2, an=an−1+3a_n = a_{n-1} + 3 defines each term from the one before, with a1a_1 as the base case. Induction proves a statement for n by assuming it holds for n - 1, the same leap of faith a recursive function makes. Once you know one idea, the other feels familiar.

Learning Path

← Before

FunctionIteration
Recursion

You are here

Know Function (parameters and return values) and Iteration (repeating steps until a condition stops them) first. Recursion replaces the loop with a function that calls itself on a smaller input, stopped by a base case. Next, Divide and Conquer uses recursion to split problems into parts, and Merge Sort applies it to sort a list by sorting its halves.

See Also