How fucken useful really is recursion?

How fucken useful really is recursion?

Jesus Christ used it when did prayer to themself, to Jehovah.

This and it makes for a neater program. I don't always want to make a new function for every little step.

Some problems really lend themselves to recursion, like the n queens problem (kind of an artificial example) or parsing json and dealing with parsed json, since json is recursive by nature; it contains json objects that themselves contain json objects, which in turn contain json objects and so on.

once I had a problem that I solved through recursion, but not tail calls, and in practice I sometimes got stack overflows
so I had to rewrite it non recursively with mutable collections (for performance)

it was a while ago and my skillz were probably not that good but sometimes recursion feels like the cool thing that real life doesn't want you to have

What language? What did the function do?

it was functional language, and some procedural generation stuff but I don't remember anything else, it's been years

I just thought it was not a functional language, since you could rewrite your program in a non-recursive way, and I was surprised you mentioned tail call elimination, since most non-functional languages don't really have tail call elimination to begin with afaik.

conceptually it can give you very elegant algorithm. pragmatically, unless you're coding in prolog, you probably want to avoid it and rewrite it non recursively with hand-rolled stacks that wont explode (like your function stack)

It is very useful in some cases.
Graph traversal, parsing json/XML/yaml etc.

A E S T H E T I C S and some problems actually need recursion to be solved, see Towers of Hanoi.
Also, it's a good brainlet filter.

essential for RNNs

It's not. Recursion causes stack overflow and thus isn't used in the real world.

If you're not trolling you're dumb.

One use that always turns up for me is in I unsorted tree traversal, exactly like what you would find on a file system. Most recently I had to use this when searching for objects in VMware folders. You ask the VMware API for the folder contents, then you must search sub folders. You recursively search through folders until you find what you're looking for.

>actually need recursion
It's been mathematically proven that everything you can accomplish with recursion, can be done iteratively.

Recursion is just easier to grasp for humans - iterative versions are more efficient but harder to code most of the time

>recursion is easier
No, it's not. Especially not in large programs.
It will invariably lead to all sorts of bugs and memory management issues.
Iterative is longer, but it's easier.

Indeed, try to traverse a binary tree w/o recursion, for most graphs recursion helps a lot.
Also for example if you want to mathematically evaluate a string containing variables recursions saves a whole of work.

I give a test to candidates at work and part of it involves graph traversal. If some idiot submitted a solution without recursion they would not be getting hired.

the tree has (2^n)-1 nodes where n > stacksize, find a node with value x

>ackerman's function

source?

How can you write recursion with these condition?

How do fuck to I parallelize recursive shit with OpenMP? That's one reason why i stick to iterative

Like everything that is touted as "the one true way" by computer scientists (microkernels, REPLs, RISC, "stateless" programming etc), in practice, it's a useless curiosity.

Almost
though recursive descent parsing is nice and good enough for parsing actual programming languages so G++ and Clang use that.

Depending how you define iteratively, you can always replace the function calls with your own stack of "stack frames" and a loop. Think about it, All code compiles to assembly, which has no function syntax, right? Just ifs and jumps.

This was a nice exercise actually, ackerman without an explicit ack() call inside of itself:

def ack(x, y):
args = [([], x, y)]

while True:
aux_args, x, y = args.pop()
if x == 0:
if aux_args:
aux = aux_args.pop()
args.append((aux_args[:], aux, y + 1))
else:
return y + 1;
elif y == 0:
args.append((aux_args[:], x - 1, 1))
else:
args.append((aux_args + [x - 1], x, y - 1))

print('ack(1, 1): {}'.format(ack(1, 1)))
print('ack(1, 2): {}'.format(ack(1, 2)))
print('ack(2, 2): {}'.format(ack(2, 2)))
print('ack(3, 2): {}'.format(ack(3, 2)))
print('ack(3, 4): {}'.format(ack(3, 4)))

It turns out I didn't have to pass copies of aux_args everywhere, at least it's still correct for the examples I provided when I put it outside next to args[]. Turns out I don't entirely get how my code works.

Really
Unless you're forcing it then you're better off with loops
Usually the shit you see in cs 101 where they force an example that could be done in two lines with a loop usually runs like shit when you do recursion

It's useful for some stuff like tree traversal.
never ever ever ever ever ever ever use it without tail call optimization though unless you like stack overflows.

? that's only an issue if you're working with a brainless language without tail call elimination, and even if you are there are ways to avoid blowing up the stack.

well it had a "mutable" keyword, that all I needed

It's a way to solve problems, just like trees, types, and anything else in CS.

If the problem doesn't require it then just don't use it.

>.pop
neck yourself

Not at all.

The absolute best case for recursion is that it's written in a way that allows the compiler to optimize it to a regular loop (tail call optimization), but that requires the language and your algorithm to support that.

There's also the ackermann function which can't be computed iteratively, but all values that can realistically be computed have been computed already, and the function is fucking useless anyway.

Use iteration, it makes your code clearer, it performs better, it's easier for you to write and it's simply better.

Recursion is for manbabies who make things harder for themselves because they think they are clever even though they have not ever written anything worthwhile.

>ackermann function which can't be computed iteratively
retard much?
of course I can write an iterative loop to calculate that function, as long as Im allowed to use a stack data structure.

inb4
>hurr using a stack is the same as recursion durr

For any task that's not easily memoizable, recursion is probably a good solution.

Collision detection for platformer games is done incredibly well with quadtrees, which lend themselves to recursion

I once used recursion to write a dungeon map generation algorithm for a senior project in high school. Efficient as fuck, still have the project and still works great.

Recursion is really good for a lot of things that you will rarely need

Youre exactly who they had in mind when they made Java.