Recursive definition of the Fibonacci numbers

3.3

In some recursive definitions, the value of the function is directly

specified not only for 0, but for the first k nonnegative integers.

The Fibonacci numbers are F(0), F(1), F(2), …, where F is defined

recursively by:

• F(0) = 0

• F(1) = 1

• F(n) = F(n-1) + F(n-2) (for n?2)

So that:

F(2) = 1+0 = 1

F(3) = 1+1 = 2

F(4) = 2+1 = 3

F(5) = 3+2 = 5

F(6) = 5+3 = 8

Previous slide

Next slide

Back to first slide

View graphic version