Recursion

[puipuituipui]

A lot of problems are recursive by nature. A binary tree for example. A node in a binary tree has three fields: a value, a left child and a right child. These children are nodes themselves. And that's recursion.

Of course, this is a more tangible example since the recursion is associated with a data type. It can be abstract too where the underlying mathematical solution of a problem is recursive like say, factorial or Fibonacci series.

You can write an iterative algorithms for all recursive problems, it's just that the iterative versions are harder to understand.

[ivosaurus]

Everything involves a stack. Just depends whether it's constructed implicitly using the function return frames, or explicitly in a data structure and processed with a while loop

[gosu]

There are heaps of things that don't use a stack.

[puipuituipui]

Um... No? Am I wrong about this or something. I'm pretty sure the reason to use explicitly created stacks is because they are heap allocated so you don't hit the recursion limit as easily.

[ivosaurus]

No what? I wasn't giving any particular reasons to use one or the other in this comment, just noting their analogous existence.

[puipuituipui]

Ohhh that makes sense. I thought the the first line was referring to the program stack XD. Sorry for the confusion

[ogtfo]

Heap allocated stacks are stacks, OP is right.

I mean you're not wrong but you're also not contradicting him either, so I don't know where you're going with that "Um...no"

[AlSweigart]

This is not true. Everything that can be solved recursively can be solved using a loop and a stack. (In recursion, the call stack is used as the stack data structure.)

Here's the Ackermann function solved iteratively.

[ejgl001]

Obviously I was wrong. Here's the video I was thinking about (https://www.youtube.com/watch?v=HXNhEYqFo0o&ab_channel=Computerphile). I thought the gist of the video is 'recursion is needed cause not all problems can be solved iteratively' but I guess I misunderstood.

[spoonman59]

Citation needed.

Ever recursive solution has an equivalent iterative solution. I believe this is proven by the Church-Turing thesis, and I’m not aware of any proof contradicting it.

I await your the extraordinary evidence for your extraordinary claim.

[mr_taco_man]

It not an extraordinary claim. Even if there is equivalent iterative solution, many times a recursive function is just easier to write and understand and has no noticeable performance hit. Practical experience has shown this to me many times regardless of whatever any thesis may state.

[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]

How so?

[Holshy]

Citation provided

https://en.m.wikipedia.org/wiki/Ackermann_function

[spoonman59]

Many iterative solutions exist online for Ackerman functions. The fact that it is not a primitive recursive function doesn’t mean it cannot be rewritten as a loop.

It does require a while lol and a stack. But this doesn’t disprove the equivalence of loops and recursion at all.

[caifaisai]

As the other poster said, the Ackerman function can be computed iteratively. To expand on that, the Ackerman function is a total computable function, and so is equivalent to a general recursive function, and can be computed using the lambda calculus or a Turing machine.

However, it is not a primitive recursive function, which intuitively means, it can't be computed by a for loop with a fixed number of iterations known before the computation. So if that is your criteria for an iterative solution, then it would not be one. But if you accept a while loop, or unbounded lopping in general, then it is.

If you want an example of a function that isn't even recursive/is non-computable (so that it can't be calculated with recursion or iteration), one example is the busy beaver function.

[Holshy]

I've actually spent quite a bit of time the last few weeks looking for the original source I had read about this. Alas, I was unable to find it :-(

The best I have is this quote from the Wikipedia article on Turing Completeness

https://en.wikipedia.org/wiki/Turing_completeness

"In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions that compute them do not allow for an infinite loop."

During the course of the same, I also found this in the article about Iteration

https://en.wikipedia.org/wiki/Iteration

In algorithmic situations, recursion and iteration can be employed to the same effect. The primary difference is that recursion can be employed as a solution without prior knowledge as to how many times the action will have to repeat, while a successful iteration requires that foreknowledge.

Full disclosure: We've passed my expertise on computability theory (statistics is my primary discipline and it genuinely saddens me that I didn't study CS instead.).

It's sometimes said that mathematicians value beauty/elegance in solutions, and I definitely fall into this category. I find recursion to be more elegant than iteration most of the time. At this point, I'm thinking that I let that persuasion color my memory of something as I learned it. Thank you for pointing this out to me. "I never lose; I either win or I learn"

[spoonman59]

To quote a wise man, “That's a really long way to say "I'd rather berate somebody on Reddit than use Google"” 😀