递归，尾递归和迭代

递归：

#include <stdio.h> 

int Recursion(int m,int n) 
{ 
    if(m==0 || n==0) 
     return 1; 
    else 
     return 2*Recursion(m-1,n+1); 
} 

void main() 
{ 
    int m,n,result; 
    m=3; 
    n=-2; 
    result=Recursion(m, n); 
    printf("%d",result); 
}

迭代

#include <stdio.h> 

int Recursion(int m,int n) 
{ 
    int returnvalue=1; 
    while(m!=0 && n!=0) 
    { 
     returnvalue=returnvalue*2; 
     m--; n++; 
    } 
    return returnvalue; 
} 

void main() 
{ 
    int m,n,result; 
    m=3; 
    n=-2; 
    result=Recursion(m,n); 
    printf("%d",result); 
}

现在我的疑惑是：

，我读了从递归改为迭代，你需要使用一个栈，并保持推迟数据并在稍后弹出。现在我在这里看不到。为什么？什么时候使用堆栈，什么时候不使用？
我的翻译版本是否正确？这尾巴是递归的，因为Recursion代码的来源是这样说的。
如何从递归版本更改为迭代版本。我真的需要一个很好的来源，我可以从这里学习。谷歌搜索没有多大帮助。

来源

2011-09-10 Kraken

您的尾部递归是错误的。尾递归函数调用只能在'return'之前发生（iow'return tailcalled（foo）;'）。 – leppie

1）当每个呼叫都有值保存时，您需要使用堆栈。在你的情况下，在递归调用之后，你不会使用更深的递归调用的值，所以没有任何东西可以保存在堆栈上。

2）如果对自己的调用是最后一件事，它就是尾递归。作为@leppie的评论，你正在执行最后一个方法调用后的2*。

3）一般的方法是使用堆栈;然而，在这种情况下，没有任何东西可以保存在堆栈上，所以你可以放弃它。

下面是一些例子，其中一个需要一个堆栈，另一个使用尾递归，另一个则不需要。

void reverseCounting(int i, int n) { 
    if (i >= n) return; 
    reverseCounting(i + 1, n); 
    cout << i << endl; 
} 

void counting(int i, int n) { 
    if (i >= n) return; 
    cout << i << endl; 
    counting(i + 1, n); 
} 

// you could just count backwards, but this is a simple example. 
void reverseCountingLoop(int i, int n) { 
    // for C you can write you own stack to do the same thing. 
    stack<int> stack; 
    //// if (i >= n) return; 
    while (!(i >= n)) { 
     //// reverseCounting(i + 1, n); 
     // save i for later 
     stack.push(i); 
     // reuse i 
     i = i + 1; 
    } 
    // unwind the stack. 
    while (!stack.empty()) { 
     //// cout << i << endl; 
     i = stack.top(); stack.pop(); 
     cout << i << endl; 
    } 
} 

void countingLoop(int i, int n) { 
    //// if (i >= n) return; 
    while (!(i >= n)) { 
     //// cout << i << endl; 
     cout << i << endl; 
     //// counting(i + 1, n); 
     // reuse i 
     i = i + 1; 
    } 
    //// nothing after the recursive call. 
}

来源

2011-09-10 06:04:30

所以我可以使用堆栈，每当我想从递归更改为迭代，或仅从尾递归？ – Kraken

如果需要，您可以每次创建一个堆栈，但只有在需要保存时才需要堆栈。对于尾递归，永远不会保存任何内容，因为递归调用后没有任何代码使用保存的值。 –

ok ..所以对于tailrecursion，转换只能使用循环完成..！谢谢。 – Kraken

你应该知道尾递归比递归更优化。编译器知道这是一个递归，可能会改变一些事情。

来源

2011-09-10 06:45:42 mathieug

递归，尾递归和迭代

回答

相关问题