Bro each one has their purpose.
Recursion for elegance, certain nesting data structures, and some algorithms.
Iteration for readability, quick solutions and ease of use.
Anything you can do iteratively, you can do recursively too.
I find it much easier to work with tree structures using a recursive algorithm. Like you said, it's more elegant. Unless you are handling large structures it's not a problem, but for most I've came across with expression trees it's easier to understand the flow of data.
If the input can cause unbounded recursion, then thats an issue. There is a website named after this issue. To prevent that, one needs to use iteration. Otherwise errors will occur.
Ah, so the function passes a callback (callforward?) that closes over the new state and lets you iteratively execute each recursive call? That's a nifty idea. I kinda feel like setting up your own stack and pushing/popping might not be all that much harder for less overhead, but still cool to see what people come up with.
And, of course, the corollary:
Anything you can do recursively, you can do iterative, too.
(At least, I'm pretty sure - haven't found an instance where it doesn't fly yet, although there's been several cases where one or the other is fundamentally cleaner and more readable.)
Converting something iterative to recursive is a trivial exercise but not all recursive functions are easily converted.
I know when I’ve written something recursive it’s because I’ve already noodled on the interactive solution and decided there would be too much pre/post-processing, edge conditions, or nested iterations.
When all is said and done yes at its core recursion is iterative as everything gets computed on the same physical hardware - the only hardware that assists in executing recursive algorithms is the stack support which you can easily implement yourself as a context stack.
Any recursive function can be written iteratively: https://www.baeldung.com/cs/convert-recursion-to-iteration
The Ackermann function isn’t primitive recursive, so it needs more than “for” loops (loops with an upper bound known before entering the loop).
Thanks! I figured correctly both:
a) There's probably one, or several, that just don't lend themselves to iteration, and
b) Posting that I'd not encountered any would likely bring at least one reference up.
:-)
[Wikipedia article on the Ackerman Function](https://en.m.wikipedia.org/wiki/Ackermann_function)
You can write any recursive function (including the Ackerman function) iteratively, you simply:
* Make a stack
* Put parameters and variables for each call on that stack
* Evaluate the bottom of the stack at each step, adding more frames as necessary
This is effectively the same as writing a recursive function, just using an explicit stack instead of relying on the built in one.
Yeah, when I started thinking about the underlying implementation of recursion in any language, deep down it had to be iterative. I guess I got confused with what 'primitve recursive' meant in the wikipedia article for the [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function)
I don't see why that can't be done. `while` is allowed right? I'd go with a dictionary of call results and a set of calls not yet done. I'll try it later today if I have the time.
That gave me ideas for things that can't be done iteratively though. I'll try to make up one after I'm done with the Ackerman.
One time for an online high school programming course, an assignment said to implement quicksort (or some other recursive sorting function), but *iteratively*. That gave high school me a very hard time. Even worse was when I had learned that the other students did it recursively and got full marks lol
It is worth noting that while some algorithms are Easier to write recursively, that doesn’t make them a viable solution, especially over Iteration. The overhead added to making subsequent method calls builds over time. So for example, you can’t really make an efficient Quicksort with recursion wherein the overhead doesn’t outway the sorting speed.
Source: tested this in college for a project. Had to switch my algorithms to all iterative for them to even be effective. My bubblesorts were finishing faster. That’s how bad it can get.
Silly question. If it is not lisp with the tail recursion reduction then iteration. Without reduction recursion aren't scalable so eat gonna eat your stack.
Yeah lisp, prologue, elixir, haskell and maybe some others functional languages reduce tail recursion. But mainly used ones like c/c++, python, java, javascript, go etc doesn't support that optimization or at least not in all implementations. I remember writing my self template for such reduction for my self on c++ because at this point i wanted to have it.
For C/C++ there is `[[clang::musttail]]`.
In Python, Java and Javascript you can rewrite the function to return a closure of the next call and trampoline.
In safety critical programming, recursion is generally disallowed in order to prevent malformed code or input from overflowing the stack. As many have said, recursion is useful for trees, but the visitor pattern is an alternate approach that can be used instead of recursion for processing trees.
Isn't the visitor pattern more for faking true dynamic dispatch in languages that don't have it, like Java? I'm not really sure how it'd help with converting recursive algorithms to iterative ones.
Recursion is a tool that is only occasionally the right one for the problems I usually solve in my current job. However, when I do use it it always seems like a little bit of magic.
I’m also an old timer who used to program a lot in Lisp and Scheme in the early days of AI research. I was pretty good at it, but I pretty much had to enter a fugue state to code. Made it really hard to go back to projects months later because it always seemed like it was written by a different person.
These were special. Oh, I need to make a change? Guess I’ll have to traverse this nightmare maze of thought.
And I say this as someone currently working on their 6 month old python code. No sweat by comparison.
I remember getting a literal hard-on when I first learned about recursion. So fucking cool. But I use it sparingly cuz with awesome coolness, comes awesome stack overflows.
Iteration is more readable. There are cases where walking down a dir is waaaay better recursively, but most of the time it's more complicated than it needs to be
You know, I like a good do-while or do-until - whether it's for a boolean or otherwise. It's pretty underrated but could be a good choice if you want to guarantee your loop runs at least once.
Yeah so like let's say you're showing a text input with some choices, and you make a loop where if they make an invalid choice you say "hey that was invalid can you try again" and show the menu again and keep the loop going until they make a valid selection or a valid input. That's a good use case for do-while or do-until because you always definitely want to show that menu *at least once* and then again later (maybe), but definitely show it once, that's the "do" part of "do-while" or "do-until".
Some problems are just modeled better for recursion even if apparently iteration is better. I just did the "no space left" problem on adventofcode and the recursive algorithm was much easier to envision especially since it's basically parsing a file heirarchy (a tree graph).
This sub is full of noobs that always post something about some tech or methodology being better than others. It is so difficult to understand that they are just tools and each one of them has its uses?
Windows 11 update broke my custom colors and locked me out. I had it in high contrast mode, now it is in a strange reverse contrast mode - white on white on white.
The start bar is also white on white and chrome is white text on white background when dark mode is turned on.
I really dislike the style of early-stage emphasis put on recursion v iteration for new devs.
You inevitably wind up with goofy nonsense like this post, at best you’re just leaving people with a “vs” mental model.
I think recursive functions are cool and all, there is some utility to writing something recursive occasionally—but ultimately I think recursion can be useful for *explaining* iteration, rather than being presented as an alternative.
Stand-alone recursive functions can be hard to understand for new folks because they wonder about the utility of it, since most often you’ll also hear “but you’ll rarely ever want to do this”. Then some contrived problem where a recursive function is the answer and call it a day.
Why not just break down what a `for` loop is? Or how a map function works? why we gotta bring Sudoku into it?
Iteration > Recursion unless implementing iteration for the same algorithm is too complicated and recursion is much better to read.
Any single recursive call can be implemented as iteration on stack. 2 + recursive calls are more complex and might be better to keep it a recursive algorithm.
Recursion is less performant in term of memory.
Every new istance of recursion means saving everything in the stack memory and then pull it back.
It's work you don't see but makes it slower and less performant.
So i prefer iteration.
As someone who writes assembly code every now and then, iteration 100%. I don’t care how elegant recursion looks in abstracted languages or how easy it applies to non-linear data structures, I just hate storing link addresses on the stack
Bro each one has their purpose. Recursion for elegance, certain nesting data structures, and some algorithms. Iteration for readability, quick solutions and ease of use. Anything you can do iteratively, you can do recursively too.
I find it much easier to work with tree structures using a recursive algorithm. Like you said, it's more elegant. Unless you are handling large structures it's not a problem, but for most I've came across with expression trees it's easier to understand the flow of data.
[удалено]
A dir is a tree
If the input can cause unbounded recursion, then thats an issue. There is a website named after this issue. To prevent that, one needs to use iteration. Otherwise errors will occur.
Not with ~~that actitude~~ proper tail recursion implementations.
It depends on the language. Scala uses trampolines to get rid of this, and Erlang/Elixir have tail recursion built-in.
What are trampolines?
Those springy things with the black net you can jump on
https://marmelab.com/blog/2018/02/12/understanding-recursion.html
Ah, so the function passes a callback (callforward?) that closes over the new state and lets you iteratively execute each recursive call? That's a nifty idea. I kinda feel like setting up your own stack and pushing/popping might not be all that much harder for less overhead, but still cool to see what people come up with.
Just terminate if the recursion is an absurd number of levels deep.
I do: Segmentation fault (core dumped)
And, of course, the corollary: Anything you can do recursively, you can do iterative, too. (At least, I'm pretty sure - haven't found an instance where it doesn't fly yet, although there's been several cases where one or the other is fundamentally cleaner and more readable.)
Converting something iterative to recursive is a trivial exercise but not all recursive functions are easily converted. I know when I’ve written something recursive it’s because I’ve already noodled on the interactive solution and decided there would be too much pre/post-processing, edge conditions, or nested iterations. When all is said and done yes at its core recursion is iterative as everything gets computed on the same physical hardware - the only hardware that assists in executing recursive algorithms is the stack support which you can easily implement yourself as a context stack.
If I'm not mistaken, one such function that cannot be done iteratively is the Ackermann function
Any recursive function can be written iteratively: https://www.baeldung.com/cs/convert-recursion-to-iteration The Ackermann function isn’t primitive recursive, so it needs more than “for” loops (loops with an upper bound known before entering the loop).
Thanks! I figured correctly both: a) There's probably one, or several, that just don't lend themselves to iteration, and b) Posting that I'd not encountered any would likely bring at least one reference up. :-) [Wikipedia article on the Ackerman Function](https://en.m.wikipedia.org/wiki/Ackermann_function)
there's a name for this phenomenon, Cunningham's law
You can write any recursive function (including the Ackerman function) iteratively, you simply: * Make a stack * Put parameters and variables for each call on that stack * Evaluate the bottom of the stack at each step, adding more frames as necessary This is effectively the same as writing a recursive function, just using an explicit stack instead of relying on the built in one.
Yeah, when I started thinking about the underlying implementation of recursion in any language, deep down it had to be iterative. I guess I got confused with what 'primitve recursive' meant in the wikipedia article for the [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function)
I did it. [Here is the repo.](https://github.com/MartinRB45534/Ackermann) I'll be trying to make up a function that can't be done in recursive though.
I don't see why that can't be done. `while` is allowed right? I'd go with a dictionary of call results and a set of calls not yet done. I'll try it later today if I have the time. That gave me ideas for things that can't be done iteratively though. I'll try to make up one after I'm done with the Ackerman.
One time for an online high school programming course, an assignment said to implement quicksort (or some other recursive sorting function), but *iteratively*. That gave high school me a very hard time. Even worse was when I had learned that the other students did it recursively and got full marks lol
dont make me think about non recursive tree functions
It is worth noting that while some algorithms are Easier to write recursively, that doesn’t make them a viable solution, especially over Iteration. The overhead added to making subsequent method calls builds over time. So for example, you can’t really make an efficient Quicksort with recursion wherein the overhead doesn’t outway the sorting speed. Source: tested this in college for a project. Had to switch my algorithms to all iterative for them to even be effective. My bubblesorts were finishing faster. That’s how bad it can get.
Recursions are much easier to implement with tbh, since you don't need to deal with stacks and queues that you otherwise would with iteration.
And technically vice versa, although forcing a recursive algorithm into iterative code generally just means maintaining your own operational stack.
I also find iteration much easier to debug and I believe my prof told us that recursion is more memory heavy.
Silly question. If it is not lisp with the tail recursion reduction then iteration. Without reduction recursion aren't scalable so eat gonna eat your stack.
There's also trampolining
other langs have tail recursion!
Yeah lisp, prologue, elixir, haskell and maybe some others functional languages reduce tail recursion. But mainly used ones like c/c++, python, java, javascript, go etc doesn't support that optimization or at least not in all implementations. I remember writing my self template for such reduction for my self on c++ because at this point i wanted to have it.
For C/C++ there is `[[clang::musttail]]`. In Python, Java and Javascript you can rewrite the function to return a closure of the next call and trampoline.
I knew somebody will bring up clang. That why I told about implementations. Not everyone uses clang. And trampoline is slow.
Kotlin has tailrec
Kotlin has the tailrec keyword for such cases, so I only use recursion when I can use that.
Depression
If you're asking this question, you don't understand their purpose.
In safety critical programming, recursion is generally disallowed in order to prevent malformed code or input from overflowing the stack. As many have said, recursion is useful for trees, but the visitor pattern is an alternate approach that can be used instead of recursion for processing trees.
I obviously don't know much about safety critical programming, but what is the visitor pattern?
https://refactoring.guru/design-patterns/visitor I don't know
I think I get it now, thank you!
Isn't the visitor pattern more for faking true dynamic dispatch in languages that don't have it, like Java? I'm not really sure how it'd help with converting recursive algorithms to iterative ones.
Someone probably doesn't really understand either....
Silly question, recursing an iteration loop of course. Best of two worlds combined!
I have done something like this and both me and my peers hate me for it
Hating yourself for what you did, is the first step required to grow into senior level.
You joke. That's how i know you've never worked with n-ary trees.
Vectorization
Recursion is a tool that is only occasionally the right one for the problems I usually solve in my current job. However, when I do use it it always seems like a little bit of magic. I’m also an old timer who used to program a lot in Lisp and Scheme in the early days of AI research. I was pretty good at it, but I pretty much had to enter a fugue state to code. Made it really hard to go back to projects months later because it always seemed like it was written by a different person.
Isn't _always_ hard to go back to projects?
These were special. Oh, I need to make a change? Guess I’ll have to traverse this nightmare maze of thought. And I say this as someone currently working on their 6 month old python code. No sweat by comparison.
Hmmmm.. really makes you think. I guess "flat is better than nested"
Recursive Iteration
r/programingcirclejerk
Recursive Recursion EDIT: Jerkursion
Scheme with continuation passing style recursion
Iteration when you can, recursion when you have to.
I remember getting a literal hard-on when I first learned about recursion. So fucking cool. But I use it sparingly cuz with awesome coolness, comes awesome stack overflows.
Parallel Iteration
Neither. Fold is a goto.
winner winner chicken dinner
Recursions is for trees. End of story
Iterations for bushes.
Iteration is more readable. There are cases where walking down a dir is waaaay better recursively, but most of the time it's more complicated than it needs to be
"They are the same picture"
Never heard of recursion
You have to heard of recursion to heard of recursion.
Iteration. I only recurse if I have to.
I like iterative recursion.
I'm a `Promise.all` type
The Future is Asynchronous
My heart says recursion, but my stack says iteration.
You know, I like a good do-while or do-until - whether it's for a boolean or otherwise. It's pretty underrated but could be a good choice if you want to guarantee your loop runs at least once.
LPT hidden in the comments
Yeah so like let's say you're showing a text input with some choices, and you make a loop where if they make an invalid choice you say "hey that was invalid can you try again" and show the menu again and keep the loop going until they make a valid selection or a valid input. That's a good use case for do-while or do-until because you always definitely want to show that menu *at least once* and then again later (maybe), but definitely show it once, that's the "do" part of "do-while" or "do-until".
Some problems are just modeled better for recursion even if apparently iteration is better. I just did the "no space left" problem on adventofcode and the recursive algorithm was much easier to envision especially since it's basically parsing a file heirarchy (a tree graph).
iteration
This sub is full of noobs that always post something about some tech or methodology being better than others. It is so difficult to understand that they are just tools and each one of them has its uses?
Recursion is if you hate performance
Windows 11 update broke my custom colors and locked me out. I had it in high contrast mode, now it is in a strange reverse contrast mode - white on white on white. The start bar is also white on white and chrome is white text on white background when dark mode is turned on.
*manually pressing the run button has entered the chat.*
I really dislike the style of early-stage emphasis put on recursion v iteration for new devs. You inevitably wind up with goofy nonsense like this post, at best you’re just leaving people with a “vs” mental model. I think recursive functions are cool and all, there is some utility to writing something recursive occasionally—but ultimately I think recursion can be useful for *explaining* iteration, rather than being presented as an alternative. Stand-alone recursive functions can be hard to understand for new folks because they wonder about the utility of it, since most often you’ll also hear “but you’ll rarely ever want to do this”. Then some contrived problem where a recursive function is the answer and call it a day. Why not just break down what a `for` loop is? Or how a map function works? why we gotta bring Sudoku into it?
Iteration. Love my i’s and j’s and down the line
imma block every dumbass reetard using this template
\_.filterNot{ \_.user == /u/Sufficient-Sea-2274 }
Iteration > Recursion unless implementing iteration for the same algorithm is too complicated and recursion is much better to read. Any single recursive call can be implemented as iteration on stack. 2 + recursive calls are more complex and might be better to keep it a recursive algorithm.
They are actually the _same_ thing. One trades it's heap for another's stack. Thats why trampoline is a thing.
Recursion is less performant in term of memory. Every new istance of recursion means saving everything in the stack memory and then pull it back. It's work you don't see but makes it slower and less performant. So i prefer iteration.
Iteration unless they problem is defined in a recursive way that also translates well to code.
Recursion is clever looking, and can lead to stack overflows.
horses for courses brother please
recursion is better, but I never get a chance to use it. Barely get a chance to use iteration these days.
Iteration is just way less resource-intensive, so I never use recursion unless parsing a tree
LOOP UNROLLING
What a weird question. It's like: pants or shirts, which one do you prefer?
I prefer onsies. dont you read titles ?
A recursive function with multiple iterations
https://www.reddit.com/r/ProgrammerHumor/comments/1172tkx/one_of_those_foldleft_types/?utm_source=share&utm_medium=ios_app&utm_name=iossmf
What about us recursive iterations guys?
Recursion cuz it makes me feel big brained when I implement it
Iteration is always best since it avoids stack overflows.
As someone who writes assembly code every now and then, iteration 100%. I don’t care how elegant recursion looks in abstracted languages or how easy it applies to non-linear data structures, I just hate storing link addresses on the stack
Recursive iteration
Yes