Project: Fibonacci Numbers with Memoization
In the previoius project we could see that computing Fibonacci Numbers with larger values of n can take a long time using recursion. Using a technique called memoization we can cache previously computed values so that we don't have to keep computing them over and over. Create an array to hold the previously computed results. Then when the function is called, look in the list first to see if the answer is there. If not, compute the Fibonacci number and put the result into the list before returning the result.
What is the largest Fibonacci Number that can be computed accurately before overflow occurs? Add a precondition to your function to prevent operation using a value that would produce an incorrect result.
See [[wikipidea or link]]
See Fibonacci1
Output
$ python3 Fibonacci2.py
Fibonacci Sequence
1: 1
2: 2
3: 3
4: 5
5: 8
6: 13
7: 21
8: 34
9: 55
10: 89
11: 144
12: 233
13: 377
14: 610
15: 987
16: 1597
17: 2584
18: 4181
19: 6765
20: 10946
21: 17711
22: 28657
23: 46368
24: 75025
25: 121393
26: 196418
27: 317811
28: 514229
29: 832040
30: 1346269
31: 2178309
32: 3524578
33: 5702887
34: 9227465
35: 14930352
36: 24157817
37: 39088169
38: 63245986
39: 102334155
40: 165580141
41: 267914296
42: 433494437
43: 701408733
44: 1134903170
45: 1836311903
46: 2971215073
47: 4807526976
48: 7778742049
49: 12586269025
50: 20365011074
51: 32951280099
52: 53316291173
53: 86267571272
54: 139583862445
55: 225851433717
56: 365435296162
57: 591286729879
58: 956722026041
59: 1548008755920
60: 2504730781961
61: 4052739537881
62: 6557470319842
63: 10610209857723
64: 17167680177565
65: 27777890035288
66: 44945570212853
67: 72723460248141
68: 117669030460994
69: 190392490709135
70: 308061521170129
71: 498454011879264
72: 806515533049393
73: 1304969544928657
74: 2111485077978050
75: 3416454622906707
76: 5527939700884757
77: 8944394323791464
78: 14472334024676221
79: 23416728348467685
80: 37889062373143906
Solution
Pure Programmer
