Hey /g/ Why someone uses recursion over iteration ? Its literally

nerd cred

>>59865293

big meaty lambdas

>>59865293
functional languages

>>59865293
It makes the code more readable for example when dealing with trees.
It's inferior to iterate code but it gets the job done in initial development.

Some problems Ate more efficiently solved with recursion. See project eular for example. I've definitely needed it several times professionally, as mentioned by someone else when it comes to tree like structures. One real world example I can think of is traversing the folder structure within vsphere.

Tail recursion > iteration

>>59865434
>>59865480
Yeah, but can be achieved with iterations too and be readable with a good code structure and good commenting and has the advantage of performance giving you control on how the iteration will occur prior to optimization. I only see advantages for iteration while recursion can lead you to hard predicable results and stackoverflow.
Right now, i have never read a good advantage yet.

>>59865293

Because the solution is elegant and if it can be done without iteration it's fine?

>>59865293

bool isRecursionGood(){
    return isRecusionGood();
}

>>59865567
You need to find a node deep in an unsorted tree and unbalanced tree. Please write me code to do this with iteration, then try it with recursion.

This is revcursion with iteration. Are you taking about something different op? How would you do this without recursion when you don't know the tree size, depth, and there's multiple children and the whole tree is unsorted and unbalance?

def traverse(obj, search_val)
  If obj,val == search_val
    return obj
  If obj.children
     obj.children.each do |child|
       found = traverse(child, search_val)
        return found if found
    end
    return false
end

Sorry typed this on my phone

The only time I see stack overflows in recursion is when you fuck up.

At worst languages handle 1000.
2^1000=1.071509e+301

>>59865293
There are times you need recursion, when you don't know the amount of loops needed. Usually the recursive method includes iteration. I've done several project eulers where this was the case. But it's always more expensive than iteration when both can be used.

Assuming you're talking about plain old recursion, usually it isn't fantastic. Optimized tail call recursion, though, has some really interesting properties, depending on the language.

Some languages just can't do it. Their engine can't into tail call recursion. Some make it obtuse and occasionally scary (Perl uses labels and gotos, if memory serves correctly, still love the language).

Tail call recursion's properties which make it superior are, among others: can handle trees of unknown size or depth, can potentially fork on multithreaded machines for searching through trees, can make very elegant solutions to some problems. Of particular note is that tail call recursion preserves the stack, and maintains a very slim memory profile, which is the key feature in some cases.

The pet problem for which tail call recursion is brought up is factorials or primes or towers of hanoi. I've personally used anonymous functions with tail call recursion to loop and conserve memory space, because a while loop had some limitations (I can't remember which, exactly) which a function did not.

If your language doesn't support tail call optimization then you have no business doing recursion in the first place.

>>59867030
You're a shit programmer if you can't figure out how to convert that into iteration.
A tree is essentially a two-dimensional linked list.
All you need to do is iterate through the nodes in both dimensions.

>>59868372
It's actually ``goto &NAME``, no labels involved.

>>59868554
No disagreement. Python doesn't use it (stack traces, but a third party module does), for example, and I would thusly avoid it there. Rust doesn't (because it wasn't a think when C was designed??? Weird rationale). It's actually rather annoying to find a list of programming languages which do or do not support tco. I suppose depending on the language you're working in, follow best practices.

As far as stack traces and debuggers go, there are solutions which circumvent the issues presented there. Depending on the debugger, of course.

Overall, though, there are reasons to use recursion, and reasons to use explicit iteration.

>>59865293
>Why someone uses recursion over iteration ?

Depending on the problem, it can be a lot simpler than using iteration.

>Its literally a bad programming practice and can lead to some stack overflow.

Everything has a limit.

I thought using loops consumes more memory?

>>59865293
makes some things simpler to read/reason about.

>>59865293
Does this mean LISP is truly a meme language?

>>59865293
tail call optimization

>>59868575
Still waiting for someone to do it. Keep in mind each parent can have unlimited children

>>59868575
I'm going to have to call you the shit programmer unless you can supply some code that is anywhere near as simple as using recursion with iteration.

Try Haskell, doesn't have any loops, only recursion. It keeps your code elegant and concise.

>>59865293
I legit don't understand this fetish for recursion either. Everything you can do with recursion can be done more efficiently with iteration.

It's just CS students trying to justify all that money they wasted on their degree, it has no real world application.

>>59865293
Recursion is always needed for when you need to find a specific file deep inside a folder in a tree-like structure. Now, try it with iteration.

>>59872603
Iteration doesn't work when you don't know the number of loops needed to solve a problem /thread

>>59865293
Variable length arrays can lead to a stack overflow but they are still useful no?

>>59872879
break if condition is met

>>59867030
>>59872603
See that example, try to do that without recursion. Protip, you can't.

>>59872923
no idea what you're talking about.

>>59872923
>>59867030
Still waiting on someone to solve this without recursion.

>>59872923
My professors rape me whenever I use break.

>>59872954
he didn't understand the problem
>>59872923what do you "break" ? You're not in a loop, you're in a loop of loops. Suppose that you are somewhere in a tree. You don't have any idea of how many nodes' children lists you'll have to loop. Iteratively you would have to do something like :
for child1 in root.children:
for child2 in child1.children:
for child3 in child2.children:
...
And a "break" will never solve the problem. First because it would break out of only one loop, second because you have no mean of "looping loops" like that without recursion.

>>59872824
Recursion with an implicit call stack can always be transformed into iteration with an explicit stack.

>literally bad
As opposed to figuratively bad? What would that even mean?

>>59865293
>Its literally a bad programming practice and can lead to some stack overflow.
That actually depends on the language and its implementation. But to answer your question: sometimes recursive code is much more readable and sensible, for example, when your data structures are also recursive.

>>59873205
legitimate use of goto

>>59872980
>>59872944
>>59870322
Frig off and do your own homework.

>>59874087
lol I'm proving that it can't be done. I haven't had homework in 20 years.

>>59867292

No. If the language supports TCO and your recursive function can be optimized then there is no difference in performance.

>>59872879
This
There's a reason programming languages do both
They don't give you two choices to do the same but one is the right one

Actual programmer here.

I've used recursion once at this job. The situation is that I have a database with a bunch of categories and each category has a parentId. I want to from the root category build a hierarchy if child categories starting from the parents.

postgres supports recursive hierarchal queries, but mysql does not, and unfortunately thats what the pajeets at my job chose, so I had to do it in code. I would grab the list of all of the categories that had a parentId = to the current category I was at and then recursively call the function again with a new parentId.

You could do it iteratively maybe if you build out your own stack? Seems like a waste of fucking time an effort and it would make the code more bloated then it needs to be.

>>59865567
Not all algorithms can be iterated over! See Ackermann's function.

>>59874218

Keep in mind I wasn't onboard when they designed the schema for the DB either. There is another way to solve it using just sql if the data is setup right by simply making a reference of the path of the child nodes.

>>59873874
You could also stop throwing random words and expecting that people will figure out the hard part for you.
Putting aside the ugliness of gotos, how the fuck could they solve this problem ? Did you ever see a not-crazy programmer replace recursion with goto ?
>>59873793
Replacing 3 lines of recursion with a full reimplementation of the stack and an unreadable iterative implementation isn't an improvement.

>>59874229

It can be if you basically reimplement the stack

#include <stack>
#include <iostream>
using namespace std;
long A(long m, long n) {
    stack<long> m_stack;
    stack<long> n_stack;
    m_stack.push(m);
    n_stack.push(n);
    while(m_stack.size()) {
        m = m_stack.top();
        n = n_stack.top();
        m_stack.pop();
        n_stack.pop();
        if (m == 0) {
            n_stack.push(n+1);
        } else if (n == 0) {
            m_stack.push(m-1);
            n_stack.push(1);
        } else {
            m_stack.push(m-1);
            m_stack.push(m);
            n_stack.push(n-1);
        }
    }
    long a = n_stack.top();
    n_stack.pop();
    return a;
}
int main (int argc, char ** argv) {
    cout << A(atoi(argv[1]),atoi(argv[2])) << endl;
    return 0;
}

>>59874269
If you use this in code worked on by others you're an asshole.

>>59874269
see >>59874262
The question is not whether you can replace a recursive function with something that doesn't call itself, but whether you can do it with reasonably readable and more efficient code.

>>59874635
It's just a a stack, and that isn't even that verbose. I think it's well worth creating your own data-structures when appropriate. If anything, recursion is harder for many people to get their heads around.

There's literally never a problem that is solvable with recursion that cannot also be solved with iteration, things would be much easier if everyone just used iterative approaches.

>>59874766
So you're telling me you would rather use
>>59874269
Than
>>59867030


Bull shit