Recursion CS Thinking Example 1

Follow the full solution, then compare it with the other examples linked below.

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

2424
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).

About Recursion

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.

Learn more about Recursion →

More Recursion Examples

Example 2 hard

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

Example 3 hard

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

Example 4 hard

Trace `countdown(3)` for `FUNCTION countdown(n): OUTPUT n. IF n > 0 THEN countdown(n-1)`. What is pr

← All Recursion Examples Recursion Concept