递归算法与并发编程能同时实现吗？

我一直在尝试在递归等求解器中实现并发。但是，我不相信我有正确的实施想法。有谁有关于有效实现递归并发的资源吗？

网友讨论：
1、对于这类问题，我认为递归就像树形结构：分支。对于数独这棵相当高的树来说，我不认为并发会比直接递归解决方案带来更多好处。不过，如果你只是随便玩玩，那么将通道/例程保持在树的顶层附近会让你获得最大的收益。前两三层

至于一般解决方案：

• 我会先用简单递归解决整个问题。
• 然后在不使用递归的情况下再添加并发性。

===========================================================

2、递归只是一种不同的习惯用法，但从根本上说与迭代并无不同，而且在某些迭代情况下，并发肯定会让你受益匪浅。

我认为，你指的是先天的顺序问题与潜在的并发问题，这与是否递归无关。

数独解题可以采用分而治之的策略，这种策略天生就是递归和并发的（另一个分而治之算法的教科书式例子是合并排序，它很容易编写递归和并发的算法，但诀窍在于限制并发程度，因为天真的方法很可能对你弊大于利。此外，还要分析性能，因为高速缓存的本地性问题也可能会伤害到自己）。由于是 IO 绑定的工作负载，我会将并发级别限制在第一级，但如果你愿意，也可以在每一级都这样做

============================================================

3、除此之外，您可以将数独谜题的解决分成可以同时解决的“部分”
例如。您从拼图中某些位置的一些数字开始。所以你把这个谜题分成几行（对于 9 x 9 的谜题来说有 9 行）——这样 9 个 goroutine 就可以在这些行上做任何工作。
一旦它们返回，您就可以将拼图分成 9 列，并在这些列上运行 9 个 goroutine。
然后对这些黑盒反复重复冲洗。

一些建议的策略是：

1. 如果为一个点设置了一个值，则将该点与同一行/列/框中所有其他点的可能值分开（如果一个点只有一个可能的值，那么这就是该点的值）（此策略将运行 9 个 goroutine ）
2. 行/列/框中的任何点是否可能具有多个值，并为该行/框/列保留唯一值（也就是说，即使该点可能有 n 个可能，但它可能是唯一一个具有a 'x'）（该策略将运行 9 个 goroutine
3. 猜测策略 - 一旦谜题达到无法通过修剪确定的程度，则找到谜题中可能数量最少但大于 1 的点，并复制谜题，以便有新的谜题副本，每个都有该点的一种可能。

====================================================
取决于你在做什么。

我的做法是，首先计算每个空格的所有可能值；这可以递归进行，但我不确定这样做能节省什么。

然后，我会将每个开放方格插入优先级队列，优先级由可能值的最少数量决定。

然后，我会采用特殊并发版本的递归步骤；弹出队列，为每个可能的值启动一个 goroutine。该 goroutine 会在棋盘的一个副本中填入该空格的该值，然后将该值从其影响的所有可能值列表中移除，建立一个新的优先级队列，并从那里开始迭代递归，直到填满棋盘，或者到达没有更多可能值的地方。

你可以让 DFS 中的每一个后裔（因为这就是你所建立的）都并发，但我认为这最终会让你付出比顶层更高的代价。

======================================================
Shawn Lee 发表了一篇论文，名为“通过线程管理和数据共享方法实现高效并行数独求解器”，该论文探讨了递归（基于树）并行性。
他介绍了使用线程来分配要解决和验证的谜题导数。您可以使用 go 例程在 go 中对类似的算法进行建模。

======================================================
使用回溯吗？如果是这样，由于算法的递归性质并不简单。您可以尝试将整个棋盘细分为 N 个不同的起始位置和/或起始值，触发 N 个 goroutine 并更快地进行暴力破解，甚至使用缓存（有点像动态编程）来避免两次尝试相同的解决方案。
其他更优化的解决方案可能更容易添加并发性，但回溯尤其困难，因为必须准确知道最后检查的配置。

​​​​​​​