请问递归实现一定能转为非递归实现吗？

Question

感觉上是，但我又想不到如何用非递归的方式实现快速排序

Answer 1

liuyubobobo 2022-06-23 10:06:17

一定可以。一个通用的转换方式是自己建立一个栈来模拟系统栈的运转过程。

我在这个课程中介绍过这个方法：https://coding.imooc.com/class/82.html 

如果你购买过这个课程，可以参考这个课程的 6-2 和 6-3.

如果你没有购买过这个课程，可以自己研究一下这三个代码：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/06-Stack-and-Queue/Course%20Code%20(C%2B%2B)/03-Non-Recursive-Implementation-of-a-Recursive-Algorithm

这三个代码是使用自己模拟系统栈的方式来做树的前中后序遍历。通常教科书中的树的前中后序遍历，因为不完全是使用模拟系统栈的方式（尤其是后序遍历），所以他们的算法差距特别大。但是如果我们使用模拟系统栈的方式，他们的代码模式是高度统一的。（就像树的前中后序遍历的递归代码其实是高度统一的一样。）

如果你理解了这个方法，应该可以“很容易地”使用这种方式把任何递归代码（包括快排）写成非递归的形式。只要你的心中有那棵递归树就好。（很容易之所以打引号，是因为期待马良肯定还是比递归高。当你深入掌握递归以后，就会发现，计算机世界中的大量问题，使用递归去思考其逻辑，是远远比使用非递归简单的。这本身就是递归的意义。）

继续加油！：）

• 提问者 慕运维2948618 #1

  哦哦，那反过来不一定成立吧？非递归的写法不一定能转为递归的写法是吗？

• liuyubobobo 回复 提问者 慕运维2948618 #2

  也一定可以。循环结构是一定可以用递归表达的。大多数纯粹地函数是编程语言不支持循环结构，但是是图灵完备的。比如 Haskell 或者 Erlang。（或者在一些纯粹地函数语言中，虽然存在循环结构，但其本质是一个“语法糖”或者是一个用递归实现的“函数”。）