# If the whole point of recursion is to break the problem into multiple smaller problems, what if those problems were solved in parallel?

So I was studying here and I was thinking if the whole point of recursion is to break the problem into multiple smaller problems, what if those problems were solved in parallel? A quick search lead me to links like this where people say it's not worth it because of context switching which makes sense, but what if instead of spawning lots of threads one has a fixed number of threads and stores the state of the recursive calls into a data structure like a stack for example, would that be a good idea to use recursion like that? If it depends on the task, what would make it so it's a good or bad approach?

• Yes it would sometimes work. E.g. quick sort, if the data-set is big enough. May 2, 2019 at 22:09

Recursion isn't really about breaking problems into smaller ones or enabling concurrency; it's about solving self-similar problems.

Consider this representation of a Binary Search Tree:

``````public class Node
{
public string key;
public Node left;
public Node right;
}
``````

That's all you need to completely represent a binary search tree. Why? Because it is a Recursive Data Type; the nodes in the `left` and `right` members each form the root of a new tree, and those members each form the root of a new tree, and so on.

Here's how you find something in a Binary Search Tree:

``````public Node Find(Node node, string key)
{
if (node == null) return null;
if (node.key == key) return node;
if (node.key < key) return Find(node.left, key);
else return Find(node.right, key);
}
``````

Simple, yes?

How well does this perform? Well, you can find any item in a balanced binary tree containing four billion nodes using 32 recursions or less.

• Naturally, this problem is trivially solved with the same number of iterations instead. May 5, 2019 at 18:35
• Sure, but not nearly as elegantly. As you already know, any recursive algorithm can also be solved iteratively. You just need to provide your own stack. May 6, 2019 at 16:29
• what about recursion max depth exceeded error? using iterators may be clumsy but seeing it does just fine
– user339013
Jun 21, 2019 at 14:59
• @who: Normally that doesn't happen unless you have an infinite recursion error. Jun 21, 2019 at 15:04
• have you tried 100 factorial with recursion?? without recursion it is possible. similar algorithm with recursion and python complains max recursion depth exceeded error (correct me if i am wrong)
– user339013
Jun 21, 2019 at 15:06

This sounds like a question of doing a divide-and-conquer problem in parallel.

People have done some actual implementations in SO, and it seems their strategy is to start to implement sequential calculation after reaching a particular depth. This would be similar to your example of a limited number of threads, since the max number of threads generated would be dependent on your sequential depth limit.

Please find their post here: https://stackoverflow.com/questions/16260879/how-to-parallelize-a-divide-and-conquer-algorithm-efficiently

Edit: It seems that many of the comments there are also contentious about whether this strategy is effective, but it's unavoidable having some overhead due to threading.

You can use recursion and parallel proccesing but it depend on the problem your solving. If the recursion method call it self two or more times in one run you can use threads to solve this. but if it call it self only one time it's pointless, for example factorial. factorial expect the result of n-1 in every run, so using parallel proccesing don't improve performance in this case.

Just because something is recursive, does not mean it's automatically faster or takes less memory. In fact, it can severely slow down the speed of a program. Take the Fibonacci numbers as an example. If you do pure recursion for these, something like:

``````int fibonacci( int n) {
if (n = 0 || n = 1) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
``````

This will result in 2n function calls - Just calculating the 20th fibonacci number already means this function is called over a million times!

If instead, you solved it iteratively (or dynamically) by saving your previous numbers, you'd only need n "runs" of a loop - that's linear!

• And there is an even better approach using matrix-multiplication for O(log n) steps. If you don't just decide to simply pre-calculate every result fitting into a tiny `int` for O(1). May 5, 2019 at 18:39
• It's not O(n^2), it's exponential
Sep 9, 2019 at 14:38
• It's 1,5something ^ n. Which is absurdly bad for a problem that is easily solved in O(n) and with some maths and harder worker in O(log n) If you create a recursive function that returns both fib(n) and fib(n-1), that runs in O(n). Feb 17 at 0:04

Quicksort can be implemented as a recursive algorithm. Now if you have say 8 cores, they can work on sub problems simultaneously. But if the sub problems are tiny, then the cost of distributing them to multiple processors is much higher than the savings.

So you would do some measuring and then find experimentally an N so that sorting N items on one processor is faster than one partitioning of N items followed by using two processors to sort each half of the result. So if your measuring tells you that the break even point is at N = 730, your code might say partition(); if the shorter half has more than 730 items then sort it using another core and sort the longer half with the current core, else sort both halfs with the current core.

You'd probably try to figure out how to partition a huge array taking advantage of multiple cores.

In my opinion recursion should only be used for problems that need a reduction step to be done at each iteration and the output used as the input for the next recursion, so in order to do the second reduction proper, the first reduction must be complete first, for problems like these parallel processing isn't feasible since it is intrinsically a sequentially dependent process.

• i am inclined to agree
– user339013
Jun 21, 2019 at 15:03