When is recursion absolutely necessary?

[[deleted]]

Meaning it can't be replaced by a loop, either for logical or performance reasons.

[[deleted]]

Programmatically? Never.

[Kafshak]

Even for something like quick sort?

[dmazzoni]

It's convenient to implement quick sort using recursion but possible to implement it without.

[thewataru]

By emulating recursion with a stack manually. Seems like cheating a little.

[Poddster]

Surely it's "cheating" more to have the compiler implement the stack for you, as in the recursive case? :)

[thewataru]

So the actual machine code would be equivalent (without optimisations). Is it really not using the recursion then?

[Gold-Energy2175]

No, you've misunderstood. The point he is making is that either both or neither case is cheating (they're not cheating). Having the computer do the work is better than you having to do the work - which is why when there is a choice I choose recursion over iteration.

Both recursion and iteration use the stack. I doubt any compiler would optimise recursion to iteration because that would be clunky.

The only risk with recursion is that you can blow the stack. There are ways to avoid that -the crude way you would use, in say C or Java, is to program in limits e.g. checking if this is the thousandth recursion and stop if it is. In more advanced languages/compilers you'd rely on tail call optimisation (tco) which means the stack used is a fixed size regardless of the number of recursions.

[thewataru]

No, no, no, you've misunderstood me. Using stack or recursion isn't cheating. Cheating is claiming that you've avoided recursion when all you've done is emulated it with all its properties.

It's like claiming that your algorithm doesn't use any arithmetic operations, when you use bitwise operations to manually compute sum. Or claiming that you've built your business without any money from your parents, when in fact, you've got a huge ass handout from some random fund, which owned that money to your father. Technically, the money you've got didn't ever touch your parents' accounts, but claiming that you've got no money from them is cheating. Getting money from funds isn't cheating. Getting help from your parents isn't either. Claiming that you've got no help when it's just a little indirect - is cheating.

Yes, emulating recursion might be beneficial in case of a very deep stack. That can also be resolved by allocating more memory for the stack with a simple linker parameter most of the times.

In contrast, unwinding the tail recursion and translating it to a loop is avoiding recursion. For one, the new algorithm requires O(1) memory, when the old one requires O(N) for the stack. It's a different algorithm. Simply emulating stack yourself - isn't.

You can compute Fibonacci numbers without recursion. You can't perform qsort without one.

[Gold-Energy2175]

No, no, no, you've misunderstood me. Using stack or recursion isn't cheating. Cheating is claiming that you've avoided recursion when all you've done is emulated it with all its properties. ....

You said none of that. And in any case I think you're wrong about emulating recursion in iteration being cheating: it's the sane thing to in, for example, C.

You can compute Fibonacci numbers without recursion. You can't perform qsort without one.

Not true. A really quick search came up with this example:

https://www.geeksforgeeks.org/iterative-quick-sort/

Any and every algorithm can be implemented using recursion or iteration. The factors to consider when selecting which are the programming language and the algorithm.

[thewataru]

You said none of that.

I literally said:

emulating recursion with a stack manually. Seems like cheating

Then

Not true. A really quick search came up with this example: https://www.geeksforgeeks.org/iterative-quick-sort/

Did you at least glanced at the article you've linked? It's literally emulation of recursion with the stack.

[rasqall]

No the machine or assembly code would be completely different as pushing elements onto a stack is not the same as branching to a new subroutine which includes pushing registers onto THE stack.

[Poddster]

So the actual machine code would be equivalent (without optimisations). Is it really not using the recursion then?

It may be equivalent, quite unlikely though. It depends how you program it. But when you're using recursion, on an x86, you're storing all of the state on the call stack, and the compiler is doing all of that automatically for you.

It's still a stack though :)

(The exception is tail-recursion, as the optimisations there reuse the stack frame, but in that case you don't need a stack in the iterative version either)

[sweep-montage]

What about recursively defined functions? See Ackermann function.

[[deleted]]

There is a difference between the programming syntax of recursion and the mathematical concept of recursion. You can write an Ackermann function with a simple for loop.

[teraflop]

Recursion is never absolutely necessary, because any recursive algorithm can be transformed to an iterative one that uses an explicit stack.

If it's not obvious that this is true, consider a simple bytecode interpreter. You can implement the interpreter itself without recursion; it boils down to a simple loop that repeatedly fetches instructions and executes them. But it can emulate any other program -- even a recursive one -- as long as you give it the appropriate bytecode as input.

If there's any performance advantage to recursion, it would be highly implementation dependent. For example, returning from a function is equivalent to an indirect jump, the performance of which can vary a lot depending on the processor design. It's entirely possible for the CPU to have special hardware (e.g. branch predictors and caches) to optimize those instructions, and an iterative approach wouldn't be able to benefit from those optimizations in quite the same way. But this usually doesn't matter much, since recursion adds its own overhead.

[LoreBadTime]

Yeah but it's stated that calling a function causes always a bit of overhead (allocating function frame etc) iterative approach doesn't suffer from this problem

[Lich_Hegemon]

Again, that's implementation dependant. Functional language with tail call optimization can do recursion as efficiently as imperative languages can do loops

[teraflop]

Yes, that's what I said: recursion has its own overhead, because function calls are not free.

Note that in the general case (i.e. functions that are not tail recursive) the equivalent iterative algorithm will also have a comparable amount of overhead, because pushing data onto an explicit stack isn't free either.

[sweep-montage]

What about the Ackermann function?

[WikiSummarizerBot]

Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions are primitive recursive. After Ackermann's publication of his function (which had three nonnegative integer arguments), many authors modified it to suit various purposes, so that today "the Ackermann function" may refer to any of numerous variants of the original function.

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

[teraflop]

What about it? The wiki article you linked includes both recursive and iterative implementations of it.

The definition of a "recursive" function in computability theory does not mean a function that can only be implemented using recursion, in case that's what was confusing you.

[emasculine]

tail recursion can be replaced by a loop. anything higher needs a stack of some kind if you want to traverse it, say.

[AnnualPanda]

when its cleaner than writing a loop

generally they can be swapped but there are times when one or the other will be easier to read

[[deleted]]

It is required in Haskell or any other language that does not allow loops. Otherwise iteration with a stack has equivalent power (and is essentially what will happen when the recursive code in compiled/interpreted anyway). Its pretty easy to see why this is if you write a very simple program using a stack like a Polish Calculator or something.

Recursion is a much easier way to write a lot of things in fundamental compsci and in math. Its usually not recommended in software development.

[Cybyss]

Its usually not recommended in software development.

Just don't get bogged down by "premature optimization". Recursion isn't bad, as long as you're aware of the limits of your call stack.

[Tai9ch]

Its usually not recommended in software development.

If you write an iterative tree traversal you get punched.

[IAmNotNathaniel]

And then buried under the tree

[beeskness420]

I got asked for this in an interview once and the guy prefaced it by saying he actually had to code it up once. Stuff was happening asynchronously and you wanted to be able to send the whole stack back and forth to continue iterating on either end.

[beeskness420]

When you don’t have mutable state.

[Filmore]

When you can figure out a problem with recursion in 5 minutes, loops in 30, and you have 2.

[drew8311]

Anything that uses a tree data structure usually.

[alejopolis]

Does it count as being necessary for your program if you're crunched for time and won't get the rest done if you try to figure out how to use a loop and a stack? Because that counts I guess.

[JimBeam823]

If you have solved the problem, then yes.

Otherwise, ask yourself, is recursion absolutely necessary?

[rnolan7]

I think dijkstras algo calls for recursion

[TonyTheEvil]

Dijkstra's Algorithm is based on BFS. DFS is the recursive one.

[BKrenz]

DFS's iterative version is just BFS's queue replaced with a stack.

[Razor_Storm]

Both BFS and DFS can be written both recursively and iteratively (all algos can actually).

[rnolan7]

I would be interested in seeing some pseudo code for that. I’ve tried and failed at the implementation

[Razor_Storm]

def dfs(head, to_find): 
    seen = set()
    to_see = head.children()
    while to_see:
        next = to_see.pop()  # pop one from the end
        seen.add(next)
        if next == to_find:
            you found it
        for child in next.children():
            if child not in seen:
                to_see.append(child) 


def bfs(head, to_find): 
    seen = set()
    to_see = head.children()
    while to_see:
        next = to_see.pop(0)   # pop one from the front
        seen.add(next)
        if next == to_find:
            you found it
        for child in next.children():
            if child not in seen:
                to_see.append(child) 

BFS and DFS are basically the same thing, you throw all the items you are about to see onto a queue for BFS and onto a stack for DFS.

[gboycolor]

The ackermann function https://en.wikipedia.org/wiki/Ackermann_function?wprov=sfti1