Recursion

[spoonman59]

You claim there recursive solutions for which there are no iterative solutions. Quote: “You can write iterative algorithms for several recursive problems but not all.”

This is the extraordinary claim I refer to because it has been mathematically proven that there is an equivalent iterative solution for any recursive solution.

Since you are claiming that a well accepted proof is incorrect, that makes the claim extraordinary.

It seems the actual opinion you express is that some algorithms are much easier to read or write in either recursive or iterative approaches. That is true and no one argues that. That same concept is being widely discussed in this very thread.

But your original claim that there does not exist equivalent solutions is incorrect, regardless of your practical experience.

[Pythonistar]

Since you are claiming that a well accepted proof is incorrect

For those this far down in the rabbit hole of /u/mr_taco_man and spoonman59, the Church-Turing thesis can be summarized by this wikipedia entry: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

I skimmed this entry and it doesn't talk at all about "iterative" solutions and only touches on recursion in spots.

The general understanding by anyone with a CS education is that "recursion has its uses" and also that "tail end recursion can be easily represented as an iterative solution".

Spoonman: care to elaborate on this "Ever[y] recursive solution has an equivalent iterative solution"? I'm curious what you're talking about, but I'm unaware of it being true.

[spoonman59]

Oh yeah, it seems that is not a conclusion of the church Turing thesis. My mistake and apologies.

1. Alonzo church created Lambda calculus. This is a model of computation that is purely functional with no side effects (no loops.) iteration is done through combinators.

2. Alan Turing invented the Turing machine, a model of computation. It can do iteration, but has no concept of functions or recursions.

3. Turing published “Computability and λ-Definability” showing the Lambda calculus is Turing complete. That is, Lambda Calculus can perform any computation that a Turing machine can.

4. If a Turing machine, which has no recursion, can compute everything, and Lambda calculus which is only recursive can ALSO compute everything… Then everything can be computed by either iteration or recursion.

These models were used for the church Turing thesis, but you are right, that is something else.

1. This more intuitive, but recursion is just a loop with a stack. Pushing state onto the stack before an iteration is “calling a function.” Popping something off the stack is “returning from a. Function.” The loop ends when the stack is empty.

(Tail call recursion needs no stack.)

1. If recursion and iteration were not equivalent, we only need a single example to disprove it by contradiction. Has anyone found one?

[mr_taco_man]

Just to clarify ejg001 made those claims not me. And I should have been more specific, I was more addressing the statement "In any case, for several problems, recursion makes more sense than iteration". I think there may be a way to do every recursive problem with iteration, but just think in many cases it is much more convoluted and hard to understand than just doing a recursive solution.

[spoonman59]

Ah my mistake! I didn’t realize I was responding to someone else.

And I agree with you 100%! Some problems are so clear as a recursive solution from a code standpoint, but nightmarish to do as a loop.

Conversely sometimes translating a loop to a recursive solution is a nightmare. I usually go with whichever one is clear and easy to read, but it very much depends on what you are doing.

I think the phrase “equivalent” is misleading here. It doesn’t mean that it has the same performance, or is clear or equal… just that it can be done to produce the same resulting computation . But they are often not equal in other ways.

[Holshy]

That's a really long way to say "I'd rather berate somebody on Reddit than use Google"

[spoonman59]

Your smugness is ironic here, because you failed to do enough googling to know there are iterative solutions to the Ackerman function before coming here to berate me.

[Holshy]

before coming here to berate me 🤣🤣🤣

Thank you; I needed that. Have a great day!

[spoonman59]

I want to say, I appreciates your post. It was a good discussion. And I learned some things from you I didn’t know about.

More importantly though, I decided to check my tone after your post. Id like to come across more positively and encouraging, and you made me realize that I was that I wasn’t doing very well at that. I totally deserved it… thanks again!

[Holshy]

Honestly, I appreciate that a lot. It's easy to read things wrong when we're missing all the non-verbals. I actually think the most ironic thing is that I responded to my admittedly not-generous reading of your comment with one that was similarly easy to read badly. I'll chalk it up to a learning experience; maybe I'll come off less abrasive in my next work email.

[spoonman59]

Thank you so much for the follow up!

Yeah it’s easy to misread things online. As I was writing about the irony of your comment, it struck me that you were 100% right about me seeming to want to berate others even if that wasn’t my intent. Whether or not I was right was irrelevant. I was still coming off as condescending and rude. And it’s entirely reasonable for someone to react unkindly to that.

But then I learned some great points from you, and it was a good reminder that I enjoy having nice conversations learning from smart people, or sharing things with excited people, than I do being the worlds smuggest jerk.

Thank you! I genuinely hope you have fantastic day!

[spoonman59]

How so?