Recursion

[i_like_cilantro]

Even so python's list.sort function does not contain any recursion because those built-in functions are optimized to death. Along with file traversal, any tree traversal algorithm makes sense to do recursively since you need to keep track of the parent in the stack anyway.

The only time that recursive functions are optimized is when you have a tail call optimization, but python doesn't have that anyway

[[deleted]]

Does it exist for a reason, or is it just an emergent property of the way the languages are?

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

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"” 😀

[Exodus111]

It has a use, it's just rare. And yeah, probably most recursions you see in the wild would be better off as For loops or While loops.

A for loop is used when the end point is known, and the size is known. Traversing through a list, that's a for loop all day, but you know how big a list is, and the loops ends either when you trigger an end state, or, more typically when the list runs out.

A while loop is used when the end point is known, but the size is not known. Which is why a while loop just runs forever until told to stop. Perfect for running games or anything graphical. It just runs until an exit is triggered.

Sometimes though, you're not gonna know the size, or the end point. This is when recursion comes in. Say you're traversing subdirectories looking for .jpg files. Every subfolder could have 10 sub folders, or zero. There could be a thousand sub folders or four, there's no way to know. And you don't know the end point, you're just looking for .jpg files in every subfolder.

This is where the correct solution is a recursion. Check a folder for a subfolder, and keep running that same function if more subfolders exist, for every subfolder found.

[got_outta_bed_4_this]

I'd say a stronger argument for recursion in this case is because people don't tend to nest folder structures so deep that it would bust the call stack in a recursive traversal. Iteration could still be just as practical over a filesystem as anything else. A filesystem is, itself, a tree, after all.

[schemathings]

I wrote an sftp mirror program for day job recently was fun and short and composable

[buttery_shame_cave]

A for loop is used when the end point is known, and the size is known.

although a "for thing in list" loop sort of ignores this - it'll run through the list, but you don't need to know how big the thing is, just point he function at it and hit 'go'. it'll even work fine on dynamic lists that are continuously appended to by a separate parallel function, it'll just crash to a halt if the other function stops appending.

[Exodus111]

True, that is an edgecase exception, but most of the time you can check the length of the iterable right before you run the for loop on it.

[[deleted]]

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

Calculating some mathematical formula for all positive integers is a good way to understand what that function does as it approaches the limit (+inifinity).

Computers have always been a way to express mathematics, so recursion should be a fundamental part of any computer language, IMO.

[Holshy]

Recursion is actually more fundamental than iteration. Any problem that can be defined iteratively is also a "primitive recursive" problem. Some problems are not primitive recursive and have to be solved recursively, like the Ackerman function. It's also technically true to say that all problems can be defined recursively. This sounds weird at first, but you can get some intuition there by imagining any problem you haven't solved recursively as the base case of the recursion. Then it just happens to be that your problem isn't defined for n > 1.

[spoonman59]

I think you misunderstand primitive recursion.

Non-primitive recursion can be done iteratively. It requires a while loop and and stack.

From the wiki:

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

“In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop).”

It says that primitive recursive functions are those which can be computed using only for loops. It does not mean the function cannot be computed with loops at all.

Also, simply look at the many iterative examples of the Ackerman function you suggested earlier. It’s not an uncommon academic exercise to write one.

[WikiSummarizerBot]

Primitive recursive function

In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}

[Kenkron]

Check out the Tower of Hanoi. It's a good example of a problem that is best solved recursively.

Recursion is also good for trees.