我正在和一个同学争论，因为他想说服我，有可能在不使用递归的情况下实现分而治之的算法。
事实真的是这样吗？
任何可以用递归实现的算法也可以非递归实现。
递归和迭代同样具有表现力：递归可以用带有显式堆栈的迭代代替，而迭代可以用尾递归代替。哪种方法更可取取决于所考虑的问题和所使用的语言。
http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursion_versus_iteration
有一件重要的事情需要理解：使用或不递归是一个实现决策。递归不是增加计算能力所必需的（至少不是图灵完备语言）。查找"尾递归"以获取有关如何将递归函数转换为非递归函数的简单示例（在divide-et-impera 算法的情况下，您可以使用此方法最多删除 1 个递归调用）。
一个可以用递归计算的函数/算法，如果没有它，也是可计算的。重要的是你实现算法的语言是否是图灵完备的。
让我们举个例子。合并排序算法也可以使用队列作为辅助数据结构以非递归方式实现，以跟踪各种合并。