Recursion CS Thinking Example 4

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

Example 4

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?

Solution

  1. 1
    Step 1: countdown(3) prints 3, then calls countdown(2); countdown(2) prints 2, then calls countdown(1); countdown(1) prints 1, then calls countdown(0).
  2. 2
    Step 2: countdown(0) prints 0, and because n > 0 is now false, the recursive calls stop. The base case is reaching n = 0.

Answer

It prints 3, 2, 1, 0. The base case is n = 0, where no further recursive call is made.
A recursive process must move toward a stopping condition. The base case prevents infinite recursion and makes the overall definition workable.

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 1 hard

Trace the recursive function: FUNCTION factorial(n): IF n <= 1 THEN RETURN 1. ELSE RETURN n * factor

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

← All Recursion Examples Recursion Concept