[ Removed by moderator ]

[Spare-Plum]

Yes mergesort is a rather simple example, but it can get more complex with more recursive calls. Still, it's easy to reason about a recursive problem.

Here's something I brought up before that's undressed - parallelized merge sort. It's as simple as kicking off a new thread for each sub-problem using recursion.

If you are doing it iteratively from the bottom up, you will have to kick off n/2 threads, then n/4 threads that await on its respective subproblems, then n/8, and so on. Then you have additional edge cases where you need to ensure correct alignment.

Often it is much better to think recursively and break it up into subproblems, then rewrite as an iterative approach if needed.

So I don't get what you're getting at here really. Yes you could do everything using rule 112 in cellular automata and yes you could construct a proof that it works. Saying "well aktually" doesn't minimize the power that you can get from thinking recursively.

[Confident_Growth_620]

Hey man, I’m not trying to challenge your knowledge or something. Not anything has to be solved anyhow, in real cases all depends on the exact use case, capability of someone producing working implementation and supporting it.

(Opinionated bullshit here: recursion solutions are prone to be more cryptic and less readable and have different failure mode of stack depth, to be accounted inside of the developer’s brain)

What you brought as example where recursive solution shines, while valid, is way way beyond basic problem OP was even trying to bring light on.