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 an expanded version of fib(N):

fib( ___ ) = _____       (base case)

fib( ___ ) = _____       (base case)

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

Fibonacci Series
N	1	2	3	4	5	6	7	8	9	10
fib(N)	1	1	2	3	5	8	13	21	34	55