The 100th Fibonacci number is already 218922995834555169026, which is not a problem in Python, but would be in other languages.
I would personally take an iterative approach. You could do a recursive approach, but if you don’t do it with memoization I don’t think you’re gonna get higher than 30 for n or something like that. With the memoization, they should be kinda the same, but in practice, the iterative approach will still be faster, because of the overhead of adding something in the call stack.
Done!
```py
fiboList = [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,
75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,
63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,
12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,
956722026041,548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,
44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,
1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,
23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,
420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,
4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,
51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026]
def fibonacci(n):
print fiboList[0:n]
```
It only goes up to the 100th, because it does get too big. I didn't know the way to calculate the numbers in code, so I just Googled these numbers.
Note that the returned object is a tuple of tuples. Each of the internal tuples is an ordered pair that specifies a move. The first item in the pair is the peg from which a disk should be taken, and the second item is the peg where the disk should go.
We’ll allow you the amount of time it takes to play the game with 64 disks by hand to solve the puzzle.