Exercise 1: The Recurrence for a Recursive Power Function — Possible Solution
====================================================================

GIVEN
------------------------------
power(x, n) = x * power(x, n-1)
power(x, 0) = 1

STEP 1: WRITING THE RECURRENCE
------------------------------
Each call makes exactly one recursive call, on an input one smaller
(n-1), plus a constant amount of extra work (one multiplication).
Following this chapter's own general shape:

  T(n) = T(n-1) + c
  T(0) = c

This is structurally identical to this chapter's own Example 1
(countdown) recurrence.

STEP 2: SOLVING BY UNROLLING
------------------------------
T(n) = T(n-1) + c
     = T(n-2) + 2c
     = T(n-3) + 3c
     = ...
     = T(0) + nc
     = c + nc
     = c(n+1)

RESULT
------------------------------
T(n) = c(n+1) = O(n)

The recursive power function makes n+1 total calls (n recursive calls
down to the base case, plus the base case itself), each doing a
constant amount of work - an O(n) algorithm overall.

WHY THIS WORKS AS AN ANSWER
------------------------------
The recurrence is written by directly matching the recursive
function's own structure (one recursive call on a smaller input plus
constant work) to this chapter's own general recurrence shape, and
solved by unrolling using exactly the same step-by-step method this
chapter's own Example 1 demonstrated.