2

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. – ctrl-alt-delor May 2 '19 at 22:09
11

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. – Deduplicator May 5 '19 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. – Robert Harvey May 6 '19 at 16:29
  • what about recursion max depth exceeded error? using iterators may be clumsy but seeing it does just fine – user339013 Jun 21 '19 at 14:59
  • 1
    @who: Normally that doesn't happen unless you have an infinite recursion error. – Robert Harvey Jun 21 '19 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 '19 at 15:06
3

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.

2

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.

1

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 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). – Deduplicator May 5 '19 at 18:39
  • 1
    It's not O(n^2), it's exponential – RiaD Sep 9 '19 at 14:38
  • You're right. Thanks! – Joe Sep 9 '19 at 18:35
-1

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 '19 at 15:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.