### Useful applications of recursion?

Posted:

**Sat May 30, 2015 6:14 am UTC**I was thinking today about this, partly from marveling over the (non)-performance of a naively-implemented Fibonacci-sequence function I did as I'm learning my way around Lisp, and partly from thinking about a recent job interview - what are some actually useful applications for recursive functions?

Because all I've seen, both in college and in job interviews, is stuff like "how would you write a function to calculate a given Fibonacci-sequence number, hint, use recursion, we really want you to use recursion here, hint hint." But the thing is, I didn't even have to think about it for long to realize why my Fibonacci function was taking several seconds to get to even the 30th number on a multi-gigaherz computer - naive, stateless recursion is just about the least effective algorithm you could possibly choose for this problem (barring some kind of "loop through every possible value and test whether it's a valid Fibonacci number" approach, which is so perverse that I have to believe someone has deployed it in a production environment,) since every recursion has to drill all the way down to 1 twice! I don't know exactly what that is, but I think we can safely call it O(appalling) - whereas a straightforward loop algorithm is O(n) and takes only a couple numbers' worth of temporary storage.

And, y'know, that's one thing in a college course, where they just want to make sure you understand how recursion works (although it's still not a very good, since they never seem to get around to explaining when you would actually want to use it,) and the simplicity of it is kind of beautiful, but in practical terms it's friggin' ridiculous. (Recursive-factorial is another popular one, that's less absurd since it's still O(n), but when you get down to an effective-performance level a straight loop is still going to beat it just from not requiring n consecutive function calls, and is no more complex.) But in a job interview? And it was clear from the way they phrased it that the recursive solution was the "correct" answer - and, of course, I can say "sure, here's how you'd do that," but I keep wanting to preface it with "well, that wouldn't be my first choice..."

But I don't want to dismiss it out-of-hand. Recursion seems like something that probably does have genuinely useful applications - I just have no idea what they are. Anybody?

Because all I've seen, both in college and in job interviews, is stuff like "how would you write a function to calculate a given Fibonacci-sequence number, hint, use recursion, we really want you to use recursion here, hint hint." But the thing is, I didn't even have to think about it for long to realize why my Fibonacci function was taking several seconds to get to even the 30th number on a multi-gigaherz computer - naive, stateless recursion is just about the least effective algorithm you could possibly choose for this problem (barring some kind of "loop through every possible value and test whether it's a valid Fibonacci number" approach, which is so perverse that I have to believe someone has deployed it in a production environment,) since every recursion has to drill all the way down to 1 twice! I don't know exactly what that is, but I think we can safely call it O(appalling) - whereas a straightforward loop algorithm is O(n) and takes only a couple numbers' worth of temporary storage.

And, y'know, that's one thing in a college course, where they just want to make sure you understand how recursion works (although it's still not a very good, since they never seem to get around to explaining when you would actually want to use it,) and the simplicity of it is kind of beautiful, but in practical terms it's friggin' ridiculous. (Recursive-factorial is another popular one, that's less absurd since it's still O(n), but when you get down to an effective-performance level a straight loop is still going to beat it just from not requiring n consecutive function calls, and is no more complex.) But in a job interview? And it was clear from the way they phrased it that the recursive solution was the "correct" answer - and, of course, I can say "sure, here's how you'd do that," but I keep wanting to preface it with "well, that wouldn't be my first choice..."

But I don't want to dismiss it out-of-hand. Recursion seems like something that probably does have genuinely useful applications - I just have no idea what they are. Anybody?