これは再帰ですか？そうではありませんか？

Question

fib_2()は再帰だとは思わないので、私は友人と議論していますが、それは自分自身を呼び出すためです。
fib_2()には、別のfib_2()の引数として使用するための戻り値がないため、そうは思わないでしょう。 私はfib_2()がfib_3()と同じだと思います。それは反復であり、再帰ではありません。

これは再帰かどうかですか？

public class Demo { 
    public static void main(String[] args) { 
     System.out.printf("fib_1 -> %d\n", fib_1(10)); 
     System.out.printf("fib_2 -> %d\n", fff(10)); 
     System.out.printf("fib_3 -> %d\n", fib_3(10)); 
    } 

    //This is recursion 
    public static int fib_1(int n) { 
     if (n == 1 || n == 2) 
      return 1; 
     return fib_1(n - 1) + fib_1(n - 2); 
    } 

    //Is this recursion or not ? 
    public static int fff(int n) { 
     int a = 1, b = 1, c = 0, count = 2; 
     return fib_2(a, b, n, c, count); 
    } 

    public static int fib_2(int a, int b, int n, int c, int count) { 
     if (count == n) { 
      return c; 
     } 
     int tmp = b; 
     b = a + b; 
     a = tmp; 
     c = b; 
     ++count; 
     return fib_2(a, b, n, c, count); 
    } 

    public static int fib_3(int n) { 
     int a = 1, b = 1; 

     for (int i = 2; i < n; i++) { 
      int temp = b; 
      b = a + b; 
      a = temp; 
     } 
     return b; 
    } 
} 

Answer 1

fib_2は再帰的です。 fffはそうではありません。

fib_2の最初の呼び出しは、2番目の呼び出しの結果を返します（したがって、 'uses'）。

やフォーマル：

再帰は二つの特性によって定義される：答え

を生成するために再帰を使用しないシナリオを終了-a

1. 単純な基本ケース（またはケース）ベースケースに向かって他のすべてのケースを減らす一連のルール

fib_2内のが最初のプロパティを満たしている場合。 fib_2の呼び出しは2番目の時間を満たします。

---

fib_3反復的です。

fib_2はではないはfib_3と等しい！ 2つの関数は、与えられた入力ごとに同じ出力を生成する場合に限り、（数学的に）等しいです！ fib_2とfib_3は異なるパラメータを持つため、これは真実ではありません。

fib_3を使用すると、副作用のようなものを考慮する必要があり、コンピュータサイエンスの方法でfffおよび/または平等のためにfib_1

に等しくすることができます。

Answer 2

fffは、それ自体を呼び出さないため、再帰的ではありません。再帰的な実装を持つfib_2が呼び出されますが、fffメソッドを再帰的にするだけでは不十分です。

fib_2は、他の一方で、教科書、再帰的である：それはcount == nのための基本ケースを持っており、それがa、b、およびcの新しい値でfib_2を呼び出す再帰的なブランチを持っています。

Answer 3

public static int fib_2(int a, int b, int n, int c, int count) { 
     if (count == n) { 
      return c; 
     } 
     int tmp = b; 
     b = a + b; 
     a = tmp; 
     c = b; 
     ++count; 
     return fib_2(a, b, n, c, count); 
    } 

私はこのコードでリクルートが起こっていると思います。