Recursion CS Thinking Example 2

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

Example 2

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

Solution

  1. 1
    Step 1: forever(1) calls forever(2), which calls forever(3), and so on infinitely.
  2. 2
    Step 2: Without a base case, the recursion never stops.
  3. 3
    Step 3: In practice, this causes a stack overflow error — the computer runs out of memory for function calls.

Answer

Infinite recursion leading to a stack overflow error.
A base case is essential in recursion. Without it, the function calls itself forever, consuming memory until the program crashes. Always ensure 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 1 hard

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

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