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