Complete Rules

A recursive definition (or program) must have two parts:

1. If the problem is easy, solve it immediately.
2. If the problem can't be solved immediately, divide it into smaller problems, then:
   • Solve the smaller problems by applying this procedure to each of them.

Here is fib(N):

fib(  ) =        (base case)

fib(  ) =        (base case)

fib( N ) = fib( N-1 ) + fib( N-2 )