Courses‎ > ‎Intro to CS - Full Year‎ > ‎Spring‎ > ‎Dyrland-Weaver‎ > ‎Work‎ > ‎

Work 28: 4/15

posted Apr 15, 2019, 6:32 AM by JonAlf Dyrland-Weaver
  • In class, we developed a recursive function that finds the nth fibonacci number. It looked like this:
    • def fib(n):
          if n < 2:
              return 1
              return fib(n-1) + fib(n-2)
  1. Using a global counter variable, print out how many times this function must run for fib(20)
  2. Create a global variable containing the list [1, 1]. These are the first 2 fibonacci numbers.
  3. Write a second fibonacci function, list_fib(n). It will also find the nth fibonacci number but it should run much faster
    • If the function looks for a fibonacci number that is already in the list, it uses the value from the list.
    • If the function looks for a fibonacci number that is not in the list, it will recursively calculate that number, then add it to the list before returning.
  4. Use the counter variable to count how many times it takes to run list_fib(20)
    1. It should be significantly faster. 
    2. In comments in your code, explain why it is so much faster.
submit this as fast_fib