How prevalent is the use of recursion in production level software?

Question

Recursion is often portrayed as something that can crash your system if not tamed properly. But recursion is really useful to deal with naturally recursively structured data like trees and all.So, is recursion widespread in real software that is used by a lot of people or is it avoided whenever possible?Is it entirely dependent on the language used?

duped · Accepted Answer

It's extremely common.Recursion only blows up if your PL has fixed size stacks and no tail call elimination. There are plenty of languages which support both, and recursion is safe.Particularly with growable stacks, the alternative to recursion is to use something that has equivalent runtime characteristics as a growable stack (even making one explicitly). That's still using recursion, it's just explicit.It is also used extensively in parsers and compilers. There's also recursive data structures, which are also extremely common.

tus666 · Answer

Quite regularly in Python, despite the stack limitation.
Why? It's sometimes the only elegant way to walk over small tree-like data structures, the depth of which you can be safely assured will never approach Python inbuilt limit (and if they did, it would always be a data error that should fail anyways).
I do wish Python had Perl-style tail-recursion though.

josephcsible · Answer

In Haskell, it's effectively mandatory in all but the simplest programs, as there's no other way to implement any form of looping. It's usually done via higher-order functions like foldr rather than explicitly, though, which mitigates almost all of the danger.

jamesfinlayson · Answer

I think I've seen it used once or twice in my career so not common.

kstenerud · Answer

Often, if the language guides people towards recursion.Almost never if it doesn't.You need strong language support, otherwise you'll be in for a world of hurt.