Sunday, May 19, 2013

Recursion is bad

Before crazy people start sending me threatening emails, I agree there is a time and place where recursion is probably ideal (Quicksort?) That being said, its better to use other options where possible. (Please do not do binary tree problems iteratively. Ok Carry on)

Repeat after me. I will never use recursion unless there is no better alternative. There are times when recursion is a necessary evil but it's an evil that should be avoided wherever possible.

Recursion eats up memory on the call stack. Every time a function is called there is going to be an overhead associated with saving register values into memory. This adds up fairly quickly when doing recursion. Since the compiler cannot really optimize recursion since it can't predict how many times it will recurse that also will contribute to the performance hit. Once recursion goes too far it causes Stack Overflow, and life just sucks.

There are people out there who call recursion 'beautiful'. I personally think loops make more sense since they don't seem as weird. Making recursive code requires a leap of faith assuming that your code is doing the correct thing its supposed to do even though your not done writing it yet. (What did I just say??)

Basically recursion is bad. But if you have to use it wash your hands afterwards. You can do recursive questions with your own stack, but I don't see the point.

No comments:

Post a Comment