Recall the definition of a recurrence relation and how it applies to the Fibonacci sequence.

Consider how the Fibonacci sequence can be broken down into smaller subproblems and how these subproblems relate to each other.

Explore the possibility of using dynamic programming to optimize the naive recursive solution by storing and reusing intermediate results.