在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。
所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。
所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
一般来说,通过简单地使用存储变量,可以将递归模拟为迭代。注意,递归和迭代通常是等价的;其中一种几乎总是可以转化为另一种。尾递归函数很容易转化为迭代函数。只需要将累加器变量设置为局部变量,并迭代而不是递归。下面是c++中的一个例子(如果不使用默认参数的话):
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
据我所知,我可能在代码中犯了一个错误,但想法是存在的。
其他回答
通常避免栈溢出的技术是递归函数,称为蹦床技术,被Java开发人员广泛采用。
然而,对于c#来说,这里有一个小的助手方法,可以将递归函数转换为迭代函数,而不需要改变逻辑或使代码难以理解。c#是一门很好的语言,用它可以做很多神奇的事情。
它的工作原理是用一个辅助方法来包装方法的各个部分。例如下面的递归函数:
int Sum(int index, int[] array)
{
//This is the termination condition
if (int >= array.Length)
//This is the returning value when termination condition is true
return 0;
//This is the recursive call
var sumofrest = Sum(index+1, array);
//This is the work to do with the current item and the
//result of recursive call
return array[index]+sumofrest;
}
变成:
int Sum(int[] ar)
{
return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
即使使用堆栈也不能将递归算法转换为迭代算法。普通的递归是基于函数的递归,如果我们使用堆栈,那么它就变成了基于堆栈的递归。但它仍然是递归。
对于递归算法,空间复杂度为O(N),时间复杂度为O(N)。 对于迭代算法,空间复杂度为O(1),时间复杂度为O(N)。
但是如果我们使用堆栈的话复杂度还是一样的。我认为只有尾递归可以转化为迭代。
另一个使用堆栈将递归函数转换为迭代函数的简单而完整的示例。
#include <iostream>
#include <stack>
using namespace std;
int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};
int GCDIter(int a, int b)
{
stack<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
我的例子是用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)))))
一般来说,通过简单地使用存储变量,可以将递归模拟为迭代。注意,递归和迭代通常是等价的;其中一种几乎总是可以转化为另一种。尾递归函数很容易转化为迭代函数。只需要将累加器变量设置为局部变量,并迭代而不是递归。下面是c++中的一个例子(如果不使用默认参数的话):
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
据我所知,我可能在代码中犯了一个错误,但想法是存在的。