在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。
所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。
所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
这个链接提供了一些解释,并提出了保持“位置”的想法,以便能够在几个递归调用之间到达确切的位置:
但是,所有这些示例都描述了递归调用进行固定次数的场景。当你遇到以下情况时,事情就变得棘手了:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
其他回答
一个系统如何接受任何递归函数并使用堆栈执行它的粗略描述:
这是为了在没有细节的情况下展示想法。考虑这个函数,它将打印出图的节点:
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。
为了执行代码,系统运行指令。当遇到函数调用时,系统将需要的信息推回到原来的位置,运行函数代码,当函数完成时,弹出关于需要继续执行的位置的信息。
即使使用堆栈也不能将递归算法转换为迭代算法。普通的递归是基于函数的递归,如果我们使用堆栈,那么它就变成了基于堆栈的递归。但它仍然是递归。
对于递归算法,空间复杂度为O(N),时间复杂度为O(N)。 对于迭代算法,空间复杂度为O(1),时间复杂度为O(N)。
但是如果我们使用堆栈的话复杂度还是一样的。我认为只有尾递归可以转化为迭代。
实际上,最常见的方法是保留自己的堆栈。下面是一个C语言的递归快速排序函数:
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
以下是我们如何通过保持自己的堆栈来实现迭代:
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
显然,这个例子没有检查堆栈边界……实际上,你可以根据最坏的情况来确定堆栈的大小。但你懂的。
通常避免栈溢出的技术是递归函数,称为蹦床技术,被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);
}
一般来说,通过简单地使用存储变量,可以将递归模拟为迭代。注意,递归和迭代通常是等价的;其中一种几乎总是可以转化为另一种。尾递归函数很容易转化为迭代函数。只需要将累加器变量设置为局部变量,并迭代而不是递归。下面是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;
}
据我所知,我可能在代码中犯了一个错误,但想法是存在的。