Saturday, November 3, 2012

Source Saturday: While vs Recursion

In a previous post, I mentioned that I had created a Haiku generator.  One response was fairly concise:
Make this recursive
Most likely, it was intended as a joke (albeit a poor one).  However, will recursion really improve getLine()?

In general, recursion leads to code that is more difficult to understand.  Given the stack-based nature of recursion, it's harder to conceptualize vs. regular iterative code.  In some situations, it's worth the extra effort to find a recursive method because an iterative solution is difficult or impossible.  One example of this is reversing a string because recursion naturally creates a stack that the coder would have to implement in an iterative function.

That said, I can't see any feasible reason why we'd need a stack for getLine() but let's be Mythbusters and try it anyway.  I used Python's timeit library to run tests on the two variations of getLine(). returns the following results:

Iterative: 11.3675792217
Recursive: 11.7112400532
So a recursive solution is slower (no surprise, as generating each function call in the stack takes up valuable number-crunching time) but not by a whole lot.  Sorry Zirak but I'll keep this solution iterative.

Finally, a Haiku about this process (not generated by Python):

Zirak says: recurse!
Never used timeit before
Turns out I am right

No comments:

Post a Comment