Recursion in a multi-threaded program

[Jud 1]

I've written several multi-threaded programs with the parallel library, usually using tasks but one or two using parallel for.  I have a new one that is more natural for parallel for.  The problem is that this is the first one that must use recursion.  Inside the loop there is some initial stuff and then it calls a procedure that calls itself, and that isn't working.

 

If the parallel loop only has one iteration, e.g. parallel.for(1,1 ... ) or parallel.for(2,2 ... ), it works.  But for actual work, with the recursion and parallel.for, it locks up.

How can I get a recursive procedure to work in a multi-threaded program?

 

[Dalija Prasnikar 1397]

Depends on the algorithm. Also, to use parallel for you will need to rewrite that algorithm to be parallel friendly.

 

From your description, your algorithm is probably not suitable, if each step, depends on the previous step result.

 

https://softwareengineering.stackexchange.com/q/238729/161734

[Jud 1]

It is nothing like Fibonacci.  It is a depth-first search on a graph.  I'm not trying to make the recursion itself recursive - each time through the loop makes an independent call to the recursive procedure.  The instances of the procedure don't have anything to do with each other and there is no global data.  That is, I need to make parallel calls to the procedure; the recursion itself is not parallel.

 

Edited March 10, 2021 by Jud

[Jud 1]

Well, now it is working.

[Jud 1]

Follow-up.

 

When I put a recursive Fibonacci function in the parallel.for and ran it on various inputs, it worked.  When I called a recursive procedure to do Depth First Search (DFS) on a graph, it would not work if it was doing more than one in parallel. 

 

But then I made a small procedure to start the recursive calls to the DFS procedure and put that small procedure inside the parallel.for instead of the actual call to the DFS procedure, it works!

 

Just in case someone asks about this.