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``    else:``        return fib(n-1) + fib(n-2)`Using a global counter variable, print out how many times this function must run for `fib(20)`Create a global variable containing the `list [1, 1]`. These are the first 2 fibonacci numbers.Write a second fibonacci function,` list_fib(n)`. It will also find the nth fibonacci number but it should run much fasterIf 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.Use the counter variable to count how many times it takes to run `list_fib(20)`It should be significantly faster. In comments in your code, explain why it is so much faster.submit this as fast_fib