# Fibonacci via Recursion and Iteration

### Age Levels:

14 - 18Introduce students to:

- How series occur in nature
- Recursive algorithms for arithmetic series, not just Fibonacci
- Iterative solutions that rely on stored data to make recursive solutions more efficient
- Informal ideas about time complexity

Students will be able to describe how to solve a class of problems like Fibonacci:

- With recursion
- With iteration that exploits data
- And articulate that when an imbedded recursive solution can be recast as an iterative one, effort (e.g. time) can be significantly reduced

This lesson introduces how to calculate an arithmetic series, specifically Fibonacci. In the first of two hour-long sessions, using a spreadsheet (e.g. Microsoft Excel or Google Drive Sheets), students are shown how to calculate a series based on two prior values (the iterative solution), and by using a user-defined function (the recursive solution). With a large enough domain, most computers will exhibit real delays in calculating the recursion for values greater than 30. In the second session, they will explore why the iterative solution is faster, and why the recursive solution significantly slows down for large values. This lesson assumes that the teacher is well versed in using spreadsheets, including copy-down formulas.

### Alignment to Curriculum Frameworks

Curriculum alignment sheet is included in PDF.

Alignment to Curriculum Frameworks