3 ms·

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

by 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.

YeGoblynQueenne 2y ago
>> 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. 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 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.
- dahart 2y ago
  > 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.
  - YeGoblynQueenne 2y ago
    >> 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. 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.

by dahart 2y ago

YeGoblynQueenne 2y ago

>> 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. 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 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.

dahart 2y ago
> 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.
- YeGoblynQueenne 2y ago
  >> 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. 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.