再帰、テール再帰と反復

Question

ここに私のコードです。

再帰：

#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); 
} 

今、私の疑問は、次のとおりです。

1. 私は繰り返しに再帰から変更することを読んで、あなたはスタックを使用して維持する必要がありますデータをプッシュして後でポップします。今私はここでそれをやっているとは思わない。どうして？スタックはいつ使用され、いつ使用されますか？
2. 私の翻訳はここでは反復的なものですか？この末尾は再帰的ですか？Recursionコードのソースがそう言いました。
3. 再帰バージョンから反復バージョンに変更する方法を教えてください。私は本当に私がこれを勉強することができる素敵な情報源が必要です。グーグルはあまり役に立たなかった。

Answer 1

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. 
} 

Answer 2

テール再帰が再帰よりも最適化されていることを知っておく必要があります。コンパイラはそれが再帰であることを知っていて、いくつかのものを変更する可能性があります。