ループを再帰に変換するにはどうすればよいですか？

Question

私は再帰をあまり理解していません。私はクラスプログラムに取り組んでいます。私はほとんどのプログラムを再帰に変換しました。だから、私の教授は私たちにループを使わせたくないし、複数のパラメータを使うことも望まない。

プログラムはハイルストーンシーケンスを実行し、問題を抱えている関数はハイルストーンシーケンスの長さを計算します。私は自分のやり方で働いていましたが、彼の基準に従っているかどうかを確認したかったのです。 （彼の基準ではありません）

私はこの機能を実行するより良い方法があるかどうかを知りたかったのです。私が試したときに抱えていた問題は、カウンターを決してリセットせず、1からnまでのハイルストーンシーケンスを合計するため、静的変数を使用できないということでした。私はハンドシム（私はそれが私が欲しかったよりもリセットされたと信じることを拒否したので）をしたときに、それが私の機能にカウントを残すことによってそれをやってみました。また、答えは必要ありません。

私はむしろ私自身でそれを理解しようとしています。だから、誰かが私に「式」またはループを再帰に変換するためのガイドを与えることができるかどうかを尋ねてきました。 参照として、私はhailstoneシーケンスの長さを見つけるhailstoneLengthコードを貼り付けます。しかし、もしあなたが私にそれをする方法を教えたいのであれば、あなたはそれがどのように機能するのか説明できれば大丈夫ですか？私はそれを解決するために最も可能性の高いいくつかの手のシミュレーションを行います。

ループ：

int hailstoneLength(int n) 
{ 
    int count = 1; 
    int u = n; 
    while(u != 1) 
    { 
     u = hailNext(u); 
     count++; 
    } 
    return count; 
} 

再帰：

int hailstoneLength(int n, int count = 1) 
{ 
    int u = n; 
    if(u != 1) 
    { 
     return hailstoneLength(hailNext(u), count + 1); 
    } 
    else // if u = 1 
    { 
     return count; 
    } 
} 

私はそれがリセットすることなく、パラメータ、または関数であることカント以来のカウントを働くいくつかの機能を行うために必要なことを考えていました。

ありがとうございました

Answer 1

まず、無関係の変数としてuを導入して画像を混乱させました。非再帰関数は、ときn == 1それを明確に再帰が停止するために書き直すことができ、再帰的な形

int hailstoneLength(int n) 
{ 
    if (n != 1) 
     return hailstoneLength(hailNext(n)) + 1; 
    else 
     return 1; 
} 

を生成することは容易であることから、この

int hailstoneLength(int n) 
{ 
    int count = 1; 
    while(n != 1) 
    { 
     n = hailNext(n); 
     count++; 
    } 
    return count; 
} 

に単純化することができます。

int hailstoneLength(int n) 
{ 
    if (n == 1) 
     return 1; 
    else 
     return hailstoneLength(hailNext(n)) + 1; 
} 

たり（これは末尾再帰形式で書くことができ、それは明らかにする）....

int hailstoneLength(int n) 
{ 
    if (n == 1) return 1; 
    return hailstoneLength(hailNext(n)) + 1; 
} 

Answer 2

これは必要な処理を行います。関数の再帰時間を追跡するためにtail-recursive関数は必要ありません。これは本質的にここで追跡しているものです。再帰関数の呼び出しに反復ループを破壊するが、私たちはここでやっているようループ不変を除去するための本当の一般式はありません

int hailstoneLength(int n) 
{ 
    int u = n; 
    if(u != 1) 
    { 
     return 1 + hailstoneLength(hailNext(u)); 
    } 
    else // if u = 1 
    { 
     return 1; 
    } 
} 

は、一般的な考え方です。

Answer 3

戻り値の型をintとして定義しましたが、hailstoneLength（hailNext（u）、count + 1）はintではないようです。

代わりに、あなたができることは、hailstoneLength（hailNext（u + 1））を返すので、次のループ反復ではhailstoneLength（n + 1）を呼び出すようになります。あなたはやろうとしている）。それが価値あるものであれば、あなたはint u = nが必要ではないと思う。

hailNextは何をしているのか分からないので、私はさらに助けることはできませんが、再帰関数でintを返すことを確実にしたいと思います（通常、複数の入力を持つことはできません）。

は参考のために、階乗を行うため、この再帰関数を見てみましょう：

int myFactorial(int integer) 
{ 
if(integer == 1) 
    return 1; 
else 
    { 
    return (integer * (myFactorial(integer-1))); 
    } 
} 

と仮定整数は5です。

それは（5 *（myFactorial（整数-1）））を返し

そこで次の反復で、整数だから、4 *（myFactorial（整数-1））を戻します。4.

あります）

など！最後には5 * 4 * 3 * 2 * 1が返されます。