Recursion – Good, Bad, or Indifferent?

For developers using imperative languages (C, C++, C#, Java, Python, etc…), recursion can seem arcane. It’s just not something encountered regularly. However, recursion is a staple of functional programming. Given the functional programming renaissance, it may be time to “bone up”. Even if you have no interest in learning a functional language, functional concepts have many benefits that can be applied to imperative programming (i.e. LINQ, yeah, who doesn’t LOVE that). This blog post is meant to give a very broad overview of recursion for developers who don’t use it much.

WTF is Recursion?

In order to understand recursion one must first understand recursion. Yeah, I know, that’s a really old joke. Moving on…

There are heaps of rather byzantine definitions floating around. However, for our purposes we are going to say that a recursive method is one that calls back to itself. This is best demonstrated via example. Consider the following function that calculates the greatest common divisor of 2 numbers.

private int GreatestCommonDivisor(int x, int y) { return y == 0 ? x : GreatestCommonDivisor(y, x % y); }

Make sure you fully grok that function before reading on. There is a lot happening in those few lines of code.

Most recursive functions can also be written iteratively. In other words, recursive functions can be rewritten using looping constructs (while, for, etc…). See the example below.

private int GreatestCommonDivisor(int x, int y) { while (true) { if (y == 0) break; var remainder = x % y; x = y; y = remainder; } return x; }

The two functions above are commensurate. So, why would one choose one over the other? Read on! More about this in the next section.

The Bad

In imperative programming languages, recursive functions should be avoided in most cases (please, no hate mail about how this isn’t true 100% of the time). Recursive functions are less efficient than their iterative counterparts. Additionally, they are subject to the perils of stack overflows. Why is this true? I’m glad you asked. Let’s consider a greatly simplified version of what happens when a function is invoked.

  1. function arguments, variables, and return address are pushed on the stack
  2. control jumps to the function
  3. function code runs
  4. function results are copied into the return value
  5. stack is rewound to it’s previous position (memory is reclaimed)
  6. control jumps back to the caller

Often times, all of the above consumes more resources than looping. Therefore, recursive method calls are less performant.

The bigger problem is that the call stack is allocated a relatively meager amount of memory (varies wildly depending on the platform). Exceeding this causes the dreaded stack overflow exception to rear it’s ugly head. Each function call eats up space on the stack like a donkey eating a waffle. That space isn’t reclaimed until the function returns. As a total SWAG, I wouldn’t trust a recursion depth of more than about a thousand. Of course, this number varies wildly depending on the platform and amount of stack space the function consumes.

Methods that employ iteration do not suffer from any of the problems outlined in this section. In spite of that, there are still some good reasons to use recursion. Read on my friend!

The Good

As demonstrated above, recursive functions are generally shorter and more elegant. In the words of the great Donald Knuth, “premature optimization is the root of all evil”. Unless your application is extremely performance critical, chances are you will never notice the few extra microseconds. The added benefit of terse and expressive code far outweighs the performance hit. Obviously, stack overflow exceptions aren’t going away. However, if the estimated recursion depth is modest there is no reason to avoid recursion. Put succinctly, if your use case is not performance critical and the estimated recursion depth is reasonable, it’s a good candidate for recursion.

Now wait a minute, I said that stack overflows aren’t going away but I also said that recursion is a staple for functional programming. How can both of these statements be true? Three words: tail call optimization. Many functional languages employ this witchery. In a nutshell, here’s what happens. If a function’s return expression is a result of a function call, the stack frame is reused instead of pushing a new one on the call stack. That’s all there is to it! Wouldn’t it be wondrous if imperative languages did this? Maybe, someday…

Wrap This Up Already

Recursion is a useful technique for making code terse and comprehensible. However, it is less performant and breeds stack overflow exceptions in non tail call optimized languages. Carefully scrutinize your use case when choosing between recursive and iterative functions.

Thanks for reading!

Comments (11) -

google plus android app 1/13/2016 10:54:30 PM

Just desire to say your article is as astounding. The clarity in your post is simply nice and i could assume you're an expert on this subject. Well with your permission let me to grab your RSS feed to keep updated with forthcoming post. Thanks a million and please carry on the rewarding work.

I am genuinely grateful to the owner of this site who has shared this enormous post at at this time.

You really make it seem so easy with your presentation but I find this topic to be actually something that I think I would never understand. It seems too complex and very broad for me. I am looking forward for your next post, I'll try to get the hang of it!

Dale Alleshouse 1/30/2016 1:54:28 PM

Let me know if I can provide you any assistance.

allow search engines 5/2/2016 4:59:38 PM

Excellent article! We will be linking to this great article on our website. Keep up the great writing.

I actually comprehended all of this!

Hey there this is kind of of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML. I'm starting a blog soon but have no coding experience so I wanted to get guidance from someone with experience. Any help would be enormously appreciated!

Normally I don't learn post on blogs, however I would like to say that this write-up very pressured me to take a look at and do it! Your writing taste has been amazed me. Thank you, very great article.

Right here is the perfect web site for anyone who would like to understand this topic. You understand a whole lot its almost hard to argue with you (not that I really will need to…HaHa). You certainly put a brand new spin on a topic that's been discussed for decades. Great stuff, just wonderful!

free voicemail 7/22/2017 7:09:29 PM

You are so interesting! I don't think I've truly read through anything like this before. So good to find another person with genuine thoughts on this issue. Seriously.. thanks for starting this up. This website is one thing that is needed on the internet, someone with a little originality!

hair clipper guide 10/20/2017 6:40:42 AM

You actually make it seem so easy with your presentation but I find this topic to be actually one thing which I believe I would never understand. It kind of feels too complex and extremely extensive for me. I am looking forward on your subsequent put up, I'll attempt to get the grasp of it!

Add comment