Recipe

Evaluate a recursive definition at a given input

Use when: you're given a base case plus a recursive rule and asked for the value at one specific input

Goal: the definition's exact value at that input, reached by unwinding down to the base case and substituting back up

Taught in Recursive definitions

1. 1

   Check that a base case actually exists, and that the recursive rule always calls a strictly smaller input, so the chain of calls must eventually reach it.

   Example

   h(n)=h(n-1)-4 for every integer n, with no stated starting value, never bottoms out: h(2)=h(1)-4=h(0)-8=\cdots forever.

   • a base case exists and every call shrinks the input — unwinding will reach a value.
   • no base case is given, or the rule points to an equal or larger input — the object is not actually defined there.

   Why: unwinding a definition that never reaches a base case only produces an endless chain, not a value.

2. 2

   Rewrite the input in terms of the next smaller input, then that input in terms of the one smaller still, continuing until a base case appears.

   Example

   With d(0)=3, d(n)=2d(n-1)+1, evaluating d(3) unwinds as d(3)=2d(2)+1, then d(2)=2d(1)+1, then d(1)=2d(0)+1.

   Why: each layer only restates the value in terms of a smaller one; nothing is computed until the chain reaches a directly stated value.

3. 3

   Starting at the base case's known value, work back up through each layer in reverse, computing one new value at a time.

   Example

   d(0)=3, so d(1)=2(3)+1=7, d(2)=2(7)+1=15, d(3)=2(15)+1=31.

   Why: this is exactly the arithmetic the recursive rule specifies, applied in the only order that has a value ready at each step.