Last active
August 11, 2023 11:19
-
-
Save louisswarren/717be69d95331aeeb506246326139022 to your computer and use it in GitHub Desktop.
How many steps does it take to compute the fibbonacci sequence recursively?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def fib_recursive(n, _mem={1: (1, 1), 2: (1, 1)}): | |
| if n not in _mem: | |
| a, x = fib_recursive(n - 2) | |
| b, y = fib_recursive(n - 1) | |
| _mem[n] = (a + b), (x + y + 1) | |
| return _mem[n] | |
| for i in range(1, 101): | |
| f, n = fib_recursive(i) | |
| print(f"{i:>3}: {f:>21} ({n:>21} steps)") | |
| """ | |
| 1: 1 ( 1 steps) | |
| 2: 1 ( 1 steps) | |
| 3: 2 ( 3 steps) | |
| 4: 3 ( 5 steps) | |
| 5: 5 ( 9 steps) | |
| 6: 8 ( 15 steps) | |
| 7: 13 ( 25 steps) | |
| 8: 21 ( 41 steps) | |
| 9: 34 ( 67 steps) | |
| 10: 55 ( 109 steps) | |
| 11: 89 ( 177 steps) | |
| 12: 144 ( 287 steps) | |
| 13: 233 ( 465 steps) | |
| 14: 377 ( 753 steps) | |
| 15: 610 ( 1219 steps) | |
| 16: 987 ( 1973 steps) | |
| 17: 1597 ( 3193 steps) | |
| 18: 2584 ( 5167 steps) | |
| 19: 4181 ( 8361 steps) | |
| 20: 6765 ( 13529 steps) | |
| 21: 10946 ( 21891 steps) | |
| 22: 17711 ( 35421 steps) | |
| 23: 28657 ( 57313 steps) | |
| 24: 46368 ( 92735 steps) | |
| 25: 75025 ( 150049 steps) | |
| 26: 121393 ( 242785 steps) | |
| 27: 196418 ( 392835 steps) | |
| 28: 317811 ( 635621 steps) | |
| 29: 514229 ( 1028457 steps) | |
| 30: 832040 ( 1664079 steps) | |
| 31: 1346269 ( 2692537 steps) | |
| 32: 2178309 ( 4356617 steps) | |
| 33: 3524578 ( 7049155 steps) | |
| 34: 5702887 ( 11405773 steps) | |
| 35: 9227465 ( 18454929 steps) | |
| 36: 14930352 ( 29860703 steps) | |
| 37: 24157817 ( 48315633 steps) | |
| 38: 39088169 ( 78176337 steps) | |
| 39: 63245986 ( 126491971 steps) | |
| 40: 102334155 ( 204668309 steps) | |
| 41: 165580141 ( 331160281 steps) | |
| 42: 267914296 ( 535828591 steps) | |
| 43: 433494437 ( 866988873 steps) | |
| 44: 701408733 ( 1402817465 steps) | |
| 45: 1134903170 ( 2269806339 steps) | |
| 46: 1836311903 ( 3672623805 steps) | |
| 47: 2971215073 ( 5942430145 steps) | |
| 48: 4807526976 ( 9615053951 steps) | |
| 49: 7778742049 ( 15557484097 steps) | |
| 50: 12586269025 ( 25172538049 steps) | |
| 51: 20365011074 ( 40730022147 steps) | |
| 52: 32951280099 ( 65902560197 steps) | |
| 53: 53316291173 ( 106632582345 steps) | |
| 54: 86267571272 ( 172535142543 steps) | |
| 55: 139583862445 ( 279167724889 steps) | |
| 56: 225851433717 ( 451702867433 steps) | |
| 57: 365435296162 ( 730870592323 steps) | |
| 58: 591286729879 ( 1182573459757 steps) | |
| 59: 956722026041 ( 1913444052081 steps) | |
| 60: 1548008755920 ( 3096017511839 steps) | |
| 61: 2504730781961 ( 5009461563921 steps) | |
| 62: 4052739537881 ( 8105479075761 steps) | |
| 63: 6557470319842 ( 13114940639683 steps) | |
| 64: 10610209857723 ( 21220419715445 steps) | |
| 65: 17167680177565 ( 34335360355129 steps) | |
| 66: 27777890035288 ( 55555780070575 steps) | |
| 67: 44945570212853 ( 89891140425705 steps) | |
| 68: 72723460248141 ( 145446920496281 steps) | |
| 69: 117669030460994 ( 235338060921987 steps) | |
| 70: 190392490709135 ( 380784981418269 steps) | |
| 71: 308061521170129 ( 616123042340257 steps) | |
| 72: 498454011879264 ( 996908023758527 steps) | |
| 73: 806515533049393 ( 1613031066098785 steps) | |
| 74: 1304969544928657 ( 2609939089857313 steps) | |
| 75: 2111485077978050 ( 4222970155956099 steps) | |
| 76: 3416454622906707 ( 6832909245813413 steps) | |
| 77: 5527939700884757 ( 11055879401769513 steps) | |
| 78: 8944394323791464 ( 17888788647582927 steps) | |
| 79: 14472334024676221 ( 28944668049352441 steps) | |
| 80: 23416728348467685 ( 46833456696935369 steps) | |
| 81: 37889062373143906 ( 75778124746287811 steps) | |
| 82: 61305790721611591 ( 122611581443223181 steps) | |
| 83: 99194853094755497 ( 198389706189510993 steps) | |
| 84: 160500643816367088 ( 321001287632734175 steps) | |
| 85: 259695496911122585 ( 519390993822245169 steps) | |
| 86: 420196140727489673 ( 840392281454979345 steps) | |
| 87: 679891637638612258 ( 1359783275277224515 steps) | |
| 88: 1100087778366101931 ( 2200175556732203861 steps) | |
| 89: 1779979416004714189 ( 3559958832009428377 steps) | |
| 90: 2880067194370816120 ( 5760134388741632239 steps) | |
| 91: 4660046610375530309 ( 9320093220751060617 steps) | |
| 92: 7540113804746346429 ( 15080227609492692857 steps) | |
| 93: 12200160415121876738 ( 24400320830243753475 steps) | |
| 94: 19740274219868223167 ( 39480548439736446333 steps) | |
| 95: 31940434634990099905 ( 63880869269980199809 steps) | |
| 96: 51680708854858323072 (103361417709716646143 steps) | |
| 97: 83621143489848422977 (167242286979696845953 steps) | |
| 98: 135301852344706746049 (270603704689413492097 steps) | |
| 99: 218922995834555169026 (437845991669110338051 steps) | |
| 100: 354224848179261915075 (708449696358523830149 steps) | |
| """ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
At one step per nanosecond, the 50th term takes 12.59 seconds, while the 100th takes 22,450 years.