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.

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.

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 Practice Mode

Related Concepts

FunctionIteration

Background Knowledge

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

functioniteration