3 ms·

I think your analysis about efficiency is specific to one kind of implementation of recursion that is not the only possible one and certainly not the most effic

I think your analysis about efficiency is specific to one kind of implementation of recursion that is not the only possible one and certainly not the most efficient one, or how it's done in Prolog. But talk is cheap so I offer the following as a proof of concept. 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). And this is its output running on SWI-Prolog and printing out statistics about its execution: ?- 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. That will run on the smallest Arduino you can find, or at least the smallest embedded system you'll likely find that runs an OS. 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 That's on my 64 GB RAM laptop. I'm saying this to show that 100k! is not a small calculation, but it can be done efficiently with tail-call optimisation. >> 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

dahart 2y ago
I think you’re misunderstanding my points. I already said (more than once) tail recursion doesn’t count - it is implemented as iteration, and factorial is trivial to do without recursion, it just doesn’t help you make a good case. The 10GB of garbage collection doesn’t help either, and implies more time spent in memory allocation and cache churn than it’s reporting. 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.
- YeGoblynQueenne 2y ago
  Yes, I guess I misunderstand your point. When did you say that tail recursion doesn't count? And why wouldn't it? That's how you implement recursion efficiently. That's the whole point of the conversation so how come it doesn't count? 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.
  - dahart 2y ago
    Tail recursion is iteration, it’s not true recursion. I said it in my first and second and fourth comments in this thread. If you didn’t notice it or you think that tail recursion is the point of this thread, it’s because you’re misunderstanding me. I’m saying that my comments about inferior performance and memory usage do not apply to tail recursion, because tail recursion optimizes out the function call and stack usage. However, tail recursion cannot always be used, so when we’re talking about recursion proper and recursion in general, it’s fair to assume we’re talking about stack frames and function calls. NASA might be okay with a fixed-bound tail recursion, but not other kinds of recursion. 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.

dahart 2y ago

I think you’re misunderstanding my points. I already said (more than once) tail recursion doesn’t count - it is implemented as iteration, and factorial is trivial to do without recursion, it just doesn’t help you make a good case. The 10GB of garbage collection doesn’t help either, and implies more time spent in memory allocation and cache churn than it’s reporting. 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.

YeGoblynQueenne 2y ago
Yes, I guess I misunderstand your point. When did you say that tail recursion doesn't count? And why wouldn't it? That's how you implement recursion efficiently. That's the whole point of the conversation so how come it doesn't count? 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.
- dahart 2y ago
  Tail recursion is iteration, it’s not true recursion. I said it in my first and second and fourth comments in this thread. If you didn’t notice it or you think that tail recursion is the point of this thread, it’s because you’re misunderstanding me. I’m saying that my comments about inferior performance and memory usage do not apply to tail recursion, because tail recursion optimizes out the function call and stack usage. However, tail recursion cannot always be used, so when we’re talking about recursion proper and recursion in general, it’s fair to assume we’re talking about stack frames and function calls. NASA might be okay with a fixed-bound tail recursion, but not other kinds of recursion. 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.