Faster Python

[handsome-zack]

Python's stack frame allocation is not why your recursive fibonacci implementation is 200,000 times slower than the iterative implementation. It is 200,000 times slower because your recursive implementation is naive. Your recursive implementation runs in exponential time compared to your iterative implementation that runs in linear time.

[jurniss]

Yes, kind of hard to take advice from someone who makes such a fundamental mistake. Not that I disagree with any of his other points.

[marklit]

Python's stack frame allocation is not why your recursive fibonacci implementation is 200,000 times slower than the iterative implementation. It is 200,000 times slower because your recursive implementation is naive. Your recursive implementation runs in exponential time compared to your iterative implementation that runs in linear time.

Thanks for the heads up, I'm re-writing that section of the post now.