在我多年的编程生涯中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。
所以，在很久以前的某个时候，我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代，但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
要寻找的一种模式是函数末尾的递归调用(所谓的尾部递归)。这很容易用一段时间来代替。例如，函数foo:
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
以调用foo结束。这可以替换为:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
这消除了第二次递归调用。
其他回答
努力使你的递归调用尾部递归(递归的最后一个语句是递归调用)。一旦你有了它，将它转换为迭代通常是相当容易的。
在谷歌中搜索“延续传递样式”。有一个转换为尾部递归样式的一般过程;还有一个将尾部递归函数转换为循环的通用过程。
要寻找的一种模式是函数末尾的递归调用(所谓的尾部递归)。这很容易用一段时间来代替。例如，函数foo:
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
以调用foo结束。这可以替换为:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
这消除了第二次递归调用。
一个系统如何接受任何递归函数并使用堆栈执行它的粗略描述:
这是为了在没有细节的情况下展示想法。考虑这个函数，它将打印出图的节点:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
例如图表: A - B > C - > show(A)将打印B, A, C
函数调用意味着保存本地状态和延续点，以便返回，然后跳转到要调用的函数。
例如，假设show(A)开始运行。函数调用在第3行。显示(B)的意思 -将项目添加到堆栈，意思是“你需要在第2行继续使用本地变量状态node=A” —到第0行，节点为B。
为了执行代码，系统运行指令。当遇到函数调用时，系统将需要的信息推回到原来的位置，运行函数代码，当函数完成时，弹出关于需要继续执行的位置的信息。
我的例子是用Clojure编写的，但是应该很容易翻译成任何语言。
给定这个函数，当n值较大时StackOverflows:
(defn factorial [n]
(if (< n 2)
1
(*' n (factorial (dec n)))))
我们可以用以下方式定义一个使用自己堆栈的版本:
(defn factorial [n]
(loop [n n
stack []]
(if (< n 2)
(return 1 stack)
;; else loop with new values
(recur (dec n)
;; push function onto stack
(cons (fn [n-1!]
(*' n n-1!))
stack)))))
其中return定义为:
(defn return
[v stack]
(reduce (fn [acc f]
(f acc))
v
stack))
这也适用于更复杂的函数，例如阿克曼函数:
(defn ackermann [m n]
(cond
(zero? m)
(inc n)
(zero? n)
(recur (dec m) 1)
:else
(recur (dec m)
(ackermann m (dec n)))))
可以转化为:
(defn ackermann [m n]
(loop [m m
n n
stack []]
(cond
(zero? m)
(return (inc n) stack)
(zero? n)
(recur (dec m) 1 stack)
:else
(recur m
(dec n)
(cons #(ackermann (dec m) %)
stack)))))
