It begins by explaining how great recursion is.
Then later it explains why you shouldn’t use it for large inputs in the two chosen languages (JavaScript and Python) to avoid blowing up the stack.
Then it argues that tail call optimisation is bad!
So when is a good time to use recursion?!?
And what is the purpose of the book?
Check out the famous NASA coding rules. Rule number one is no recursion. :P https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...
When I was a game programmer, recursion was to be avoided at all costs.
Even as a past graphics researcher, I’ve used recursive flood-fill as part of several research papers, and recursive flood-fill on a large image will blow your stack, so I always translate it into a heap allocation and implement recursion using an iterative algorithm with breadcrumbs for backtracking. It’s common for there to be a way to increase the stack size, but it’s just really annoying and sometimes not possible to always be able to do that on any machine you want to run on.
One case where recursion or something that looks like recursion is used in production code is when dealing with tree data structures. Those are common, and traversing them is common. Recursion is acceptable for that - though people who care about performance will still optimize it into an iterative algorithm whenever possible (which is most of the time).
How so?
Do you mean "in Python" or similar languages, or do you mean in general? I write all my code in Prolog basically and there it's all recursion, no iteration. There's no iteration constructs. The Prolog interpreter has tail-call optimisation and you learn to use it soon enough.
Anyway let's not be all dogmatic like that. Rules always have exceptions (including this one ha ha) so there's no point in being so absolute about things.
>> Check out the famous NASA coding rules. Rule number one is no recursion. :P https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...
Edit: Rule no 1 from NASA is "avoid complex control flow". From your link:
1. Avoid complex flow constructs, such as goto and recursion.
> How so?
Stack + function call recursion is almost always slower and more memory intensive than alternatives, not to mention risk of stack overflow, so most people who care about perf and mem will opt out anyway. Tail recursion isn’t included, because it optimizes out the function call, and tail recursion is iteration anyway.
If tail recursion isn’t an option, it means a tree or multi-branch recursion, which is generally speaking difficult to reason about and difficult to bound, so error prone. People who care about safety, like NASA, avoid recursion for those reasons. I’m sure they will use recursion when it’s the only choice, or the best choice. Choice of data structure might affect whether recursion is best.
> I write all my code in Prolog
Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…?
I think the 2nd rule ("All loops must have fixed bounds. This prevents runaway code.") refers to numerical bounds, so if you take it literally it would also eliminate e.g. while loops with a boolean condition, but I don't know if that's the intention. In NASA, with very expensive equipment on the line, maybe; but for most other environments that would be an onerous requirement.
In any case you can turn any recursion with non-numeric bounds to one with numeric bounds easily. You do that by adding a parameter that counts the recursion steps and exits if the count exceeds a limit. For added security, you can do this check in each "clause" (literal or figurative) of the recursive procedure, not just the boundary condition. Then you have depth-limited recursion and bobs your ankle. Or Bob is your uncle, I'm never sure about that one.
>> Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…?
Most of my Prolog coding has been for my PhD and post-doc research of course but I'm now in my third industry contract where I work almost exclusively with Prolog (the rest is a bit of shell scripting and the like). I don't want to say what the industry is, or the job, but as a for instance my two previous Prolog industry gigs were in an AI startup and the other working on a legacy system for management of rental car fleets, both in France two years ago. The car system was written in the '90s and it had changed many hands since then so it was a royal mess and I didn't stay long working on it but I recently spoke with one of the other devs and it's still going.
There's plenty of that legacy Prolog expert system code around, all left over from the '90s, written before the winter. Sicstus, the biggest commercial Prolog vendor, used to brag on their landing page that if you've booked any air travel recently then chances are you used a Prolog-based system, which shouldn't come as a surprise. After all, every time you use online banking, you are using a system based on COBOL and running on a mainframe. That claim has recently disappeared from the Sicstus site though and I don't know what that means. Anyway Prolog coders occasionally hear about gigs working on stuff like that through the grapevine, but judging from my experience those are mainly maintained by programmers who have never seen Prolog before in their lives, until they're thrown in at the deep end an have to make do.
But I see you're making a distinction between "research and education" and "production code"? Why's that? The code I write for my research is production code. I can tell you that with a straight face because I've worked in the industry many years before I did my PhD and my Prolog code is much more stable, and maintainable to boot, than 90% of the rickety, held together with bits of string and gaffer tape, "production" code I worked with as an industry code monkey.
And btw I'm still a code monkey. That's what makes code "production": who writes it, not who it is for.
Btw my post-doc Prolog code had to run on a robot that cost a few thousand quid (I'm in the UK) so it had to be industrial strength. I never got to test it because my funding er expired. In academia, you have to be careful who you're telling hard, technical truths to. So now I'm working in the industry.
Yes NASA’s rule is intended to prevent loops with only boolean conditions. Everyone (i.e. people who did not write the code) should be able to know for certain by glancing at a loop whether it will finish, and fixed bounds gets you most of the way there. It is fine if you put a fixed call count on the recursion, assuming that recursion is actually the best choice. It’s just that actual recursion is almost never the actual best choice. Having a fixed call count and a fixed recursion depth nearly always suggest that the problem can be easily translated to iteration, and iteration is cheaper. Even something as simple as using a simulated stack structure to replace function calls is usually preferable to burning memory with stack frames and wasting registers and cycles passing parameters around. People who do high performance work or just care about efficiency don’t question these things.
NASA’s rules aren’t weird when it comes to other organizations that do safety-critical code. Even video games, like I mentioned used to do nearly everything on NASA’s list. Embedded code on small devices still does all of this; car manufacturers follow the same rules. When memory is very small or limited, and when crashes have high consequence and are unrecoverable, the situation is completely different than a grad student sitting at a terminal.
Their rules aren’t very onerous either, most of the time, they just require changing habits and thinking differently. Once you get used to them, just like with any coding practices, there are simple patterns you can follow to implement just about anything.
One exercise that might(?) be fun for you is take some of your research code and port it to the smallest Arduino you can buy, and get it to run. Even if Prolog is an option on that platform, you might find that standard recursion is not.
“Production code” is a fairly common/standard term (Google it and browse multiple answers) that does mean in part who it’s for. The term is meant for situations where code is usually written by teams, most often large teams, and where the code is written in service of a product, and will be run by people other than the authors of the code. Production code is not a comment on the quality of the code nor of the choice of language, but it does mean the code will be tested by a QA department and that it will be run under uncontrollable conditions by people who are not experts or coders.
If you write code for your PhD and you run it yourself, it’s not production code, period, no matter how stable or high quality you believe it to be. For sure there are cases where research code and production code overlap. They are relatively rare, but you might be in that part of the Venn diagram.
This is my factorial predicate in Prolog, tail-recursive style:
%! factorial(+N,-Factorial) is det.
%
% Calculate the Factorial of N
%
factorial(0,1):-
!.
factorial(N, F):-
factorial(N, 1, F).
%! factorial(+N,+F,-G) is det.
%
% Business end of factorial/2.
%
factorial(1,F,F):-
!.
factorial(N,F,G):-
F_ is N * F
,N_ is N - 1
,factorial(N_,F_,G).
?- time( factorial(100_000, _N) ), format('~e~n',[_N]).
% 199,999 inferences, 0.672 CPU in 1.184 seconds (57% CPU, 297673 Lips)
2.824229e+456573
true.
?- statistics.
% Started at Sun Jan 05 16:47:25 2025
% 0.672 seconds cpu time for 546,365 inferences
% 6,574 atoms, 4,766 functors, 3,441 predicates, 51 modules, 134,446 VM-codes
%
% Limit Allocated In use
% Local stack: - 20 Kb 2,432 b
% Global stack: - 508 Kb 380 Kb
% Trail stack: - 30 Kb 384 b
% Total: 1,024 Mb 558 Kb 383 Kb
%
% 22,105 garbage collections gained 9,936,079,752 bytes in 0.063 seconds.
% 4 atom garbage collections gained 1,573 atoms in 0.000 seconds.
% 7 clause garbage collections gained 156 clauses in 0.000 seconds.
% Stack shifts: 2 local, 7 global, 7 trail in 0.000 seconds
% 2 threads, 0 finished threads used 0.000 seconds
true.
Note that the above is measuring all utilisation since I started up SWI-Prolog, not just to run my code (e.g. 3,441 predicates is all the SWI-Prolog libraries).
If I try to do the same calculation on the Windows 11 Calculator (switch to "Scientific" version), I get the following output:
Overflow
>> People who do high performance work or just care about efficiency don’t question these things.
I'll try not to be hurt by your words :P
BTW, I am including (and NASA is talking about) embedded systems without an OS. Most of my game programming career involved platforms with no OS.
And when did we switch from "smallest Arduino" to "system with no OS"? I'm pretty sure that if you keep looking for the smallest platform on which you can run something, anything, you'll find a point you can make and prove, but that's kind of meh. You're not going to run a SAT solver, a planner or an image classifier on an Arduino with 512 KB RAM. You're not going to run Doom on a bank card either. Not because of recursion, because of everything else.
And if you can't transform recursion into iteration, that's a procedure you can't run without recursion anyway.
In my mind, I was assuming and including no-OS scenarios from the start, you just assumed an OS because you’re using threads and garbage collection and memory allocation. NASA’s computers on the space shuttle and rovers haven’t historically run OSes, and I assumed you might have known that. Little computers like ECUs in cars don’t run OSes either. Console video games before about 15 years ago also rarely had an OS. The Nintendo Wii didn’t have one, nor any Nintendo console before that. We never switched, I’m clarifying now because you specified an Arduino with an OS. I was talking about safety-critical, embedded, and small memory systems from the start. This point is very relevant because it’s one of the reasons that recursion is to be avoided. Doom does run on very tiny computers without an OS, like a calculator. I don’t think Doom uses any recursion or heap allocation (except maybe to initialize) or garbage collection.
I’ve never seen a recursive algorithm that can’t be transformed into iteration, or where the recursion can’t be emulated with a faster iterative mechanism and smaller memory footprint than function calls. I doubt that one exists. Tail recursion is an example of trivial recursion automatically transforming function calls into iteration.
Primitive recursive functions are the ones that can be "unrolled" in iterative loops. There are functions that are recursive, but not primitive recursive, like the Ackermann function (https://en.wikipedia.org/wiki/Ackermann_function). Those cannot be replaced by iteration.
I think you're putting far too much trust into "I haven't seen" and not considering the fact that there is more to see.
No, I was being cheeky. The fact that recursion can always be transformed into iteration has been proven. There is no such thing as a “procedure that can’t run without recursion”, which I assumed you already knew, and you might want to keep in mind if you want to keep defending recursion.
So do you have any real-world examples where recursion is preferred? This sub-thread started because you were taking umbrage with my claim that recursion is for education and not often used in production code. So far your examples are proving my point, 100% of your examples are classroom problems and not things people need in practice. List reversing might be the most common, and it’s very rare for someone to need to implement it (languages and libraries usually provide it), and far rarer still to need to implement it recursively in practice. Factorial of large numbers and Ackermann function are purely academic exercises.
There is such a thing. Non-primitive recursive functions can't be converted to iteration.
I'm sorry but where did I give examples that are "100% classroom problems"?
I gave examples of production code that use Prolog, therefore recursion since Prolog has no iteration constructs: the three jobs in the industry I've held, and the airline software from Sicstus. I can also add IBM's Watson (it used Prolog), Datalog databases (recursion is the point), and the SWI-Prolog website which is running on an http server implemented in Prolog (they call that "eating their own dogfood"). Those are all things that people need in practice and not "classroom problems". There's plenty more Prolog code running in the wild but obviously I don't know every program anyone has ever written using Prolog.
There's also code in Answer Set Programming (e.g. I'm aware of planners for robotics applications), Haskell (e.g. xmonad, a windows manager in Haskell) and plenty of code people write in Scheme, Scala, etc Lisps, that also don't have iteration constructs. There's plenty of recursion in "real world" and "production" situations. But I get the feeling you don't work with it, so you just don't believe it exists. That's not a great way to reason about things.
That’s not true, I think you’re misunderstanding the article you linked to. Primitive recursive functions require fixed bounds, but that is not the same thing as all iteration. The Church-Turing thesis proves that anything you call recursion can be iterated.
> I'm sorry but where did I give examples that are "100% classroom problems"?
I answered that question in the comment you replied to.
> But I get the feeling you don't work with it, so you just don't believe it exists. That's not a great way to reason about things.
Well, to that I offer that writing incorrect assumptions and straw-man responses isn’t a great way to communicate. I actually see recursion every day, and I still stick by what I said. I even work on a team that builds recursive hardware that accelerates traversing recursive data structures. To me it really seems like you’re still not understanding my point about call stacks vs iteration. I’m sorry my posts are making you feel defensive. Maybe you missed the part where I mentioned that if you work in a language like Prolog that offers no choice, you don’t need to worry about it? The time to worry about it is when there’s a choice, like in C++ or JavaScript or Python. Keep using tail recursion, that’s a good way to avoid some of the problems with recursion!
>> Recursion is great for CS education, but recursion should be rarely/never used in production code. Tail call recursion is one exception to that - I see it in production code occasionally. But tail call recursion is limited to cases of 1-dimensional recursion that can be transformed into iteration - and iteration is better anyway, so even tail calls need some extra justification for use in production code.
"... recursion should be rarely/never used in production code" and "even tail calls need some extra justification for use in production code". Then you listed the JPL coding guidelines that say "avoid recursion". And now you're saying that what you really meant was that yes, you should use recursion, and tail recursion, but that doesn't count because it can be replaced by iteration anyway? Then why not avoid the replacement service and have all your loops be iterative in the first place? Or is that your argument? I really can't tell. And I'm getting the feeling that you don't know exactly what you're arguing for yourself, especially if you say (big reveal) you are working with recursion everyday. What's this all about now?
>> That’s not true, I think you’re misunderstanding the article you linked to. Primitive recursive functions require fixed bounds, but that is not the same thing as all iteration. The Church-Turing thesis proves that anything you call recursion can be iterated.
Right, so now we're talking about unbounded iteration? Again that's not the impression I got from the discussion upthread. Is that the good, safe, NASA-compliant kind of coding practices you support? I don't think it is.
>> Keep using tail recursion, that’s a good way to avoid some of the problems with recursion!
Now you're just being patronising. I was hoping we could have a robust disagreement without taking the piss, but I guess this one too has gone the way of all the conversations on the internet. Let's end this hear then, I'll let you have the last word (since I wrote a bit already myself).
And no hard feelings from me. Communication is difficult.
Btw, this is interesting:
>> I even work on a team that builds recursive hardware that accelerates traversing recursive data structures.
If you want to say a couple of words about what that is, I'd be curious to hear.
Jesus Christ, I was just trying to be nice. Your defensiveness is repeatedly leading to misunderstanding and getting in the way of us having a productive conversation.
> Right, so now we’re talking about unbounded iteration?
You’re conflating multiple different topics here. NASA doesn’t allow unbounded iteration. That’s a separate topic from whether recursion can theoretically be transformed into iteration.
Recursion can always be transformed into iteration. That statement is not and never was dependent on what NASA does. There is no such thing as a recursive function that can’t be iterated. In practice, iterating is as efficient or more efficient than using a call stack. This is still and always was my point. If you’re using a call stack for recursion, you are wasting memory and cycles, which is one of the reasons “Software developed in Prolog has been criticised for having a high performance penalty compared to conventional programming languages.” https://en.wikipedia.org/wiki/Prolog#Limits
I work on ray tracing hardware, which is conceptually recursive, uses recursive tree data structures, and often implemented using recursion. We make it faster by transforming the recursion into specialized iterative hardware, and also algorithms that do iteration in place of recursion. Computer graphics is full of algorithms that are conceptually recursive and yet always more efficient in practice if you avoid using call recursion and implement them iteratively instead. Character rig animation is one example. And browsers do this for rendering HTML.
And rule number 3 is no heap allocation.
I didn't think I'd find this, so I went digging. Sure enough:
The disadvantage of tail recursion is that it requires rearranging your recursive function so that the last action is returning the recursive call’s return value. This can make our recursive code even more unreadable.
Tail recursive functions require rearranging their code to make them suitable for the tail call optimization feature of the compiler or interpreter.
Personally, I take the stance that the tail recursion technique should never be used.
> And what is the purpose of the book?
To straw-man functional programming with a one-two punch of "I already have that" and "it's bad" so devs never leave Python/JS land to find this stuff out for themselves ;)
A bizzare comment at best, from someone writing a book on recursion.