Recursion CS Thinking Example 3

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

Example 3

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

Solution

  1. 1
    Step 1: FUNCTION sum(n): IF n == 1 RETURN 1. ELSE RETURN n + sum(n-1).
  2. 2
    Step 2: sum(5) = 5+sum(4) = 5+4+sum(3) = 5+4+3+sum(2) = 5+4+3+2+sum(1) = 5+4+3+2+1 = 15.

Answer

1515
The recursive sum builds up the total by adding n to the sum of all numbers below it, eventually reaching the base case of 1.

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