Recursion Examples in CS Thinking

Start with the recap, study the fully worked examples, then use the practice problems to check your understanding of Recursion.

This page combines explanation, solved examples, and follow-up practice so you can move from recognition to confident problem-solving in CS Thinking.

Concept Recap

A technique where a function calls itself to solve progressively smaller instances of the same problem. Every recursive solution has two parts: a base case that stops the recursion, and a recursive case that breaks the problem into a smaller version of itself.

Russian dolls—open one, find a smaller one inside. Repeat until you reach the smallest.

Read the full concept explanation →

How to Use These Examples

  • Read the first worked example with the solution open so the structure is clear.
  • Try the practice problems before revealing each solution.
  • Use the related concepts and background knowledge badges if you feel stuck.

What to Focus On

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

Common stuck point: Without a base case, recursion never ends—the program crashes with a stack overflow error.

Sense of Study hint: When writing a recursive function, first define the base case—the simplest version of the problem that can be answered directly. Then define the recursive case—how to reduce the current problem to a smaller version. Always verify that each recursive call moves closer to the base case.

Common Mistakes to Watch For

Before you work through the examples, skim the mistake guide so you know which shortcuts and sign errors to avoid.

Recursion Mistakes

Worked Examples

Example 1

hard
Trace the recursive function: FUNCTION factorial(n): IF n <= 1 THEN RETURN 1. ELSE RETURN n * factorial(n-1). Call factorial(4).

Solution

  1. 1
    Step 1: factorial(4) = 4 * factorial(3).
  2. 2
    Step 2: factorial(3) = 3 * factorial(2). factorial(2) = 2 * factorial(1). factorial(1) = 1 (base case).
  3. 3
    Step 3: Unwind: 2*1=2, 3*2=6, 4*6=24.

Answer

24
Recursion is when a function calls itself. Every recursive function needs a base case (when to stop) and a recursive case (that makes progress toward the base case).

Example 2

hard
What happens if a recursive function has no base case? For example: FUNCTION forever(n): RETURN forever(n+1).

Practice Problems

Try these problems on your own first, then open the solution to compare your method.

Example 1

hard
Write a recursive function `sum(n)` that returns the sum 1 + 2 + ... + n. Trace sum(5).

Example 2

hard
Trace `countdown(3)` for `FUNCTION countdown(n): OUTPUT n. IF n > 0 THEN countdown(n-1)`. What is printed, and what is the base case?
← Back to Recursion Common Mistakes Practice Mode

Background Knowledge

These ideas may be useful before you work through the harder examples.

functioniteration