I've been writing my own programs for many years now, and I think I used recursion about two or three times so far. In each case for a binary tree or similar. Oh, and in one program I use it for generating fractal trees in 3D, and I've also used it for an expression parser. If you can use iteration instead of recursion to solve the same problem, and there is no performance hit for doing that, I'd use iteration every time. The main reason there is because it is way way easier to debug.
But sometimes you do have to use recursion, for performance reasons and because it is natural to the task. Very hard I'd imagine to write a good binary tree search without it.
It's a good technique to know about. But if you find you tend to use iteration instead of recursion most of the time, I'd say you are probably a good software engineer myself :).
That is unless you program in Lisp which I understand is naturally recursive, so that's different, but I don't have experience of using it.
If you need to do recursion you can probably find example code that does something similar to what you want, in the rare cases where you need it. And if so - best to use that because it is already debugged, especially if it is a much used e.g. open source or just a highly regarded library or such-like.
Though in rare situations you may need to write your own recursion.
I'll end with a few examples from my own code, rare situations where I did encounter recursion and there was no readily available code to use for the situation. In the first two cases I wrote it recursively. In the third case I converted it into an iteration.
If you want to write your own expression parser, it probably needs to be recursive. I wrote my own expression parser for Tune Smithy to parse formulae entered by the user and convert them to doubles. Nowadays I'm sure there must be easily available libraries for this, but it was a while back I did this.
I wrote my own recursive code to do this:
What is Virtual Flower?
I could have done it non recursively. But in that case it was a naturally recursive problem, and it needed to output code in VRML which is also a language that works well with recursion. So the whole thing I thought was well worth writing recursively despite the extra difficulties for debugging it due to that.
In my Tune Smithy program, on the other hand, I generate fractal tunes, and basically it is recursive. But - I actually program it in an iterative way because that is far easier to debug and also - it makes it easier to generate the sequence just a little at a time - it is unlike the 3D trees because when playing music you play only one note or a few notes at a time and don't need to have all the notes of the melody presented to the listener at once.
So, here is an example - a recursively defined melody played in Tune Smithy - but it is actually programmed iteratively as I decided that that was going to be both better for performance and easier to debug.
The heart of the program is a routine that traverses an array of 130 elements and increments values from the bottom of the array to the top for each new note. That number 130 is hard coded into the program as a constant - I could easily change it and increase it to a larger number (and have no idea why I chose that particular number, maybe because it is 2 more than 128 which is a 10000000 in binary) - but already it creates melody lines that typically even with the shortest two note seed would last for millions of years before they have to repeat due to hitting this recursion limit. So,anyway, I've never encountered any situation where it needs to be higher.
If I did it from top down, as a recursion, then I'd need to control the recursion to generate just the first note of the melody, then just the second note of the melody, and so on, tricky to do, especially if the end result is essentially an infinite sequence.
Or I could have generated it all at once by recursion, like the 3D trees, and cap at a certain number of recursion levels. But if you do that, you may find you generate more notes, or fewer notes, than the user wants. While the way I do it, you calculate only for the notes actually played.
So I think that's a rare case where you get performance benefits from converting a recursion into an iteration.
You can probably always convert a recursion into an iteration if you cap it at a fixed number of levels of recursion - not sure if that is a theorem - but I found it easy enough to do.
And also - even if you stick with normal recursion, there is a practical limit also - the maximum size of stack - though it is very rare on a modern computer that you'd hit that limit if you set the stack size for your program high enough.
But sometimes you do have to use recursion, for performance reasons and because it is natural to the task. Very hard I'd imagine to write a good binary tree search without it.
It's a good technique to know about. But if you find you tend to use iteration instead of recursion most of the time, I'd say you are probably a good software engineer myself :).
That is unless you program in Lisp which I understand is naturally recursive, so that's different, but I don't have experience of using it.
If you need to do recursion you can probably find example code that does something similar to what you want, in the rare cases where you need it. And if so - best to use that because it is already debugged, especially if it is a much used e.g. open source or just a highly regarded library or such-like.
Though in rare situations you may need to write your own recursion.
I'll end with a few examples from my own code, rare situations where I did encounter recursion and there was no readily available code to use for the situation. In the first two cases I wrote it recursively. In the third case I converted it into an iteration.
EXPRESSION PARSER
If you want to write your own expression parser, it probably needs to be recursive. I wrote my own expression parser for Tune Smithy to parse formulae entered by the user and convert them to doubles. Nowadays I'm sure there must be easily available libraries for this, but it was a while back I did this.
VIRTUAL FLOWER PROGRAM - PROGRAMMED RECURSIVELY
I wrote my own recursive code to do this:
What is Virtual Flower?
I could have done it non recursively. But in that case it was a naturally recursive problem, and it needed to output code in VRML which is also a language that works well with recursion. So the whole thing I thought was well worth writing recursively despite the extra difficulties for debugging it due to that.
TUNE SMITHY - CODING AND PERFORMANCE REASONS FOR CONVERTING IT INTO AN ITERATION
In my Tune Smithy program, on the other hand, I generate fractal tunes, and basically it is recursive. But - I actually program it in an iterative way because that is far easier to debug and also - it makes it easier to generate the sequence just a little at a time - it is unlike the 3D trees because when playing music you play only one note or a few notes at a time and don't need to have all the notes of the melody presented to the listener at once.
So, here is an example - a recursively defined melody played in Tune Smithy - but it is actually programmed iteratively as I decided that that was going to be both better for performance and easier to debug.
The heart of the program is a routine that traverses an array of 130 elements and increments values from the bottom of the array to the top for each new note. That number 130 is hard coded into the program as a constant - I could easily change it and increase it to a larger number (and have no idea why I chose that particular number, maybe because it is 2 more than 128 which is a 10000000 in binary) - but already it creates melody lines that typically even with the shortest two note seed would last for millions of years before they have to repeat due to hitting this recursion limit. So,anyway, I've never encountered any situation where it needs to be higher.
If I did it from top down, as a recursion, then I'd need to control the recursion to generate just the first note of the melody, then just the second note of the melody, and so on, tricky to do, especially if the end result is essentially an infinite sequence.
Or I could have generated it all at once by recursion, like the 3D trees, and cap at a certain number of recursion levels. But if you do that, you may find you generate more notes, or fewer notes, than the user wants. While the way I do it, you calculate only for the notes actually played.
So I think that's a rare case where you get performance benefits from converting a recursion into an iteration.
You can probably always convert a recursion into an iteration if you cap it at a fixed number of levels of recursion - not sure if that is a theorem - but I found it easy enough to do.
And also - even if you stick with normal recursion, there is a practical limit also - the maximum size of stack - though it is very rare on a modern computer that you'd hit that limit if you set the stack size for your program high enough.
About the Author
Robert Walker
Writer of articles on Mars and Space issues - Software Developer of Tune Smithy, Bounce Metronome etc.Studied at Wolfson College, Oxford
Lives in Isle of Mull
4.8m answer views110.4k this month
Top Writer2017, 2016, and 2015
Published WriterHuffPost, Slate, and 4 moreHuffPost, Slate, Forbes, Newsweek, Business Insider, and Science 2.0