facebook twitter mail share

Fibonacci via Recursion and Iteration

Lesson Focus 
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.

Age Levels:

14 - 18
Objectives 

Introduce 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
Anticipated Learner Outcomes 

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 
Lesson Activities 

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.

Categories 

Alignment to Curriculum Frameworks
comments powered by Disqus

Search Lesson Plans

and/or

 
Quickstart: we have resources for Students, Parents, Teachers, and Guidance Counselors