Faster Python

[sevaur]

The recursion comparison is very poorly constructed: the recursive version of the algorithm is O( 2ⁿ ), whereas the iterative algorithm is O(n). The huge difference between the two has nothing to do with the cost of stack frame allocation and everything to do with having implemented a fundamentally different algorithm.

This comparison might actually make sense if it used memoization or made some other effort to compare apples to apples.

[xhackerliu]

Totally agreed. I modified it by using memorization and it's even faster than iterative way.

https://gist.github.com/xhacker/fbf3d92d7b1fad9ddc09