5. Fibonacci numbers

The following equations define Fibonacci numbers recursively:

The last equation applies when N > 1. For example, the first ten Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

Write a program that calculates Fibonacci numbers recursively, non-recursively, and via a cache table holding Fibonacci values.