I have a recursive function. The function will call itself with various different values depending on the data it gets, so the arity and depth of recursion is not known: each call may call itself zero or more times. The function may return any number of values.
I want to parallelise it by getting goroutines and channels involved. Each recursion of inner
runs in its own goroutine, and sends back a value on the channel. The outer function deals with those values.
func outer(response []int) {
results := make([]int)
resultsChannel := make(chan int)
inner := func(...) {
resultsChannel <- «some result»;
// Recurse in a new goroutine.
for _, recursionArgument in «some calculated data» {
go inner(recursionArgument)
}
}
go inner(«initial values»);
for {
result := <- resultsChannel
results = append(results, result)
// HELP! How do I decide when to break?
}
return results
}
The problem comes with escaping the results channel loop. Because of the 'shape' of the recursion (unknown arity and depth) I can't say "finish after n events" and I can't send a sentinel value.
How do I detect when all my recursions have happened and return from outer
? Is there a better way to approach this?
You can use a sync.WaitGroup
to manage the collection of goroutines you spawn: call Add(1)
before spawning each new goroutine, and Done
when each goroutine completes. So something like this:
var wg sync.WaitGroup
inner := func(...) {
...
// Recurse in a new goroutine.
for _, recursionArgument := range «some calculated data» {
wg.Add(1)
go inner(recursionArgument)
}
...
wg.Done()
}
wg.Add(1)
go inner(«initial values»)
Now waiting on wg
will tell you when all the goroutines have completed.
If you are reading the results from a channel, the obvious way to tell when there are no more results is by closing the channel. You can achieve this through another goroutine to do this for us:
go func() {
wg.Wait()
close(resultsChannel)
}()
You should now be able to simply range
over resultsChannel
to read all the results.