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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

To add onto the others:

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 2ⁿ 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!

Answer 5

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.

Answer 6

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.