2

基本的に、私はシーケンスを特定の数まで与えるプログラムを書きたいと思っています。では、20 番目の数字か何かに行きたいとしましょう。if()ステートメントを使用するだけで、その番号までのシーケンス内の各番号の値を見つけるように、再帰的に反復する方法を知りたいです。私が知っているのはforループでそれを行う方法だけなので、コードはありません。これは私が必要とするアプローチではありません。

私は少なくともこれを知っています：

if n = 1 || n = 0
   return n;
else 
    return F(n-1) + F(n-2);

コード：

class Fibonocci {

    public static int factorial(int i,int n) { 
        System.out.println(i);

        if(i==n || n==0 || n==1) {  // base case;  when i = n, we're done.
            return n; 
        } else {
            return i + 1 + factorial(i+2,n); // iterative case; we're still adding values up.
        }
    }

    public static void main(String[] args)
    {
        Fibonocci test= new Fibonocci();
        System.out.println( test.factorial(0,10) );
    }
}

私はそれを試してみましたが、他にもたくさんの試みをしましたが、まだ困惑しています. 私はそれが行くことを知っています0 1 1 2 3 5 8 13 21 34...

4

2 に答える 2

5

驚くかもしれませんが、コードはほぼ完成しています。私の感じでは、あなたはまだ再帰に慣れていないようです。

繰り返し実行できることは、再帰的に実行できます。

次のように考えてください: ループ (for、while、do-while) には反復ステップと、それが完了したかどうかを確認する条件があります。たとえば、1 から n までのすべての数値を加算すると、次のようになります。

int sum = 0;
for(int i = 1; i <= n; i++) { // Condition to check completion
    sum += i;  // iterative step
}

これを再帰関数に変換するには、基本ケースと呼ばれる完了の条件と、反復ステップまたは反復ケースが必要です。合計すると、私の基本ケースは次のいずれかになりますi==n。

public int sum(int i, int n) {
    if(i == n) {  // base case;  when i = n, we're done.
        return n; 
    } else {
        return i + sum(i+1, n); // iterative case; we're still adding values up.
    }
}

これをフィボナッチ法に当てはめれば、きっとうまくいくと思います。いいえ、適切な引数を使用して関数呼び出しでラップすれば問題ありません。

さらなる明確化: コールはどのように展開されますか?

合計方法に戻ると、1 から 10 までの数値を合計したいとしましょう。呼び出しはどのように展開されますか?

繰り返し

実際には、コール スタックで多くのことを行う必要はありません。ループを回っています。ただし、毎回何が起こっているかを総合することはできます。

int sum = 0;
for(int i = 1; i <= 10; i++) {
    sum += i;
}

これがループを通してどのように見えるか:

Cycle #1: sum=1
Cycle #2: sum=3
Cycle #3: sum=6
Cycle #4: sum=10
Cycle #5: sum=15
Cycle #6: sum=21
Cycle #7: sum=28
Cycle #8: sum=36
Cycle #9: sum=45
Cycle #10: sum=55
Sum = 55

これまでのところ正しいようです。

毎回1 つの要素を取得し、それを集合的な合計値に追加しているだけです。本質的に、1+2+3+4+5+6+7+8+9+10 は次のように分解されます。

sum += 1 // 1 now
sum += 2 // 3 now
sum += 3 // 6 now
...
sum += 10 // 55 now

再帰的に、値が収集される方法に違いはありませんが、わずかに異なる方法で行われます。

再帰的に

この呼び出しを調べます。

public int sum(int i, int n) {
    return n == i ? n : i + sum(i+1, n); // ternary if-else statement, the exact same as the if-else in the above sum method.
}

1 + sum(2, 10)
1 + 2 + sum(3, 10)
1 + 2 + 3 + sum(4, 10)
1 + 2 + 3 + 4 + sum(5, 10)
1 + 2 + 3 + 4 + 5 + sum(6, 10)
1 + 2 + 3 + 4 + 5 + 6 + sum(7, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + sum(8, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + sum(9, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + sum(10, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
55

基本的に、再帰呼び出しでもシリアル呼び出しと同じことを行っています。展開はちょっと面白いですが、慣れれば難しくないです。

ここからは、ぜひ試してみてください。実験することを恐れないでください。ここで提供される情報は、開始するのに十分です。

于 2012-04-18T01:01:23.837 に答える
2

再帰階乗関数を書くことであなたを助けましょう：

階乗法は次のように定義されます。

 if n == 0 || n == 1 return 1; else return n * F(n - 1);

これは Java で次のように記述できます。

public int factorial(int n) { 
   if(n == 0 || n == 1) { 
       return 1;
   } else { 
       return n * factorial(n - 1);
   }
}

ですから、あなたが知っていることを考えると、フィボナッチ数列に適応してテストするのに十分だと思います.

于 2012-04-18T00:56:40.940 に答える