Pure Programmer

## 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.

$g++ -std=c++17 Fibonacci2.cpp -o Fibonacci2 -lfmt$ ./Fibonacci2 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