フィボナッチメソッドでテール再帰を実装するにはどうすればよいですか？

Question

私は大量のフィボナッチ数列を計算しようとしています。なぜ大きな整数を使用しているのですか？私は約10000までそれを得ることができますが、私はスタック空間を使い果たします。私はスタックとヒープスペースを増やすことができますが、尾の再帰がスペースの問題を回避できることは私の理解です。ここに私のコードです。

public class FibRecursion{ 

static BigInteger[] fval; 

public static void main(String[] args) { 

    int index; 

    Scanner input = new Scanner(System.in); 

    index = input.nextInt(); 


    fval = new BigInteger[index + 1]; 


    System.out.println(fib_rec(index)); 


} 


public static BigInteger fib_rec(int index){ 


    BigInteger result = BigInteger.ONE; 

    if(index <= 2){ 
     return result; 
    } 

    else{ 
     if(fval[index] != null){ 
      result=fval[index]; 
     } 
     else{ 
      result = fib_rec(index-1).add(fib_rec(index-2)); 

      fval[index] = result; 

     } 
     return result; 
    } 
} 
} 

Answer 1

これはフィボナッチの私の好きな実装です。

再帰的ですが、O（n）ではなくO（2^n）で実行されます。

public int fib(int n) { 
    return recursiveFib(0, 1, n); 
} 

public int recursiveFib(int a, int b, int n) { 
    if (n == 0) { 
    return a; 
    } 
    return recursiveFib(b, a+b, n-1); 
} 

ここで、あなたの末尾再帰の必需品について、またはそれが助けになるかどうかはわかりません。また、このロジックを中心に実際のOO実装を行う必要があります。

Answer 2

したいシリーズは可能性を達成するための単純な再帰：

public class FibRecursion{ 

    private static BigInteger[] fval; 

    public static void main(String[] args) { 

     int index = 10; 
     fval = new BigInteger[index]; 
     fib(0,1,0,index); 
     System.out.println(Arrays.toString(fval)); 
    } 

    public static void fib(long a, long b, int index, int endIndex) { 

     if (index >= endIndex) { 

      return ; 
     } 

     fval[index] = BigInteger.valueOf(a).add(BigInteger.valueOf(b)); 
     index++; 
     fib(b, a+b, index , endIndex); 
    } 
} 

スタック制限を回避するには、再帰の深さを制限し、いくつかの「作品」で復活を行うことができます。ここでは10に限定深さで計算50個の要素の直列、（RECURRSION_DEPTH = 10）の一例である。もちろん

public class FibRecursion{ 

    private static BigInteger[] fval; 
    //limit of the recursion depth. valid values are >=2 
    private final static int RECURRSION_DEPTH = 10; 

    public static void main(String[] args) { 

     int index = 50; 
     fval = new BigInteger[index]; 

     BigInteger aValue = BigInteger.valueOf(0); 
     BigInteger bValue = BigInteger.valueOf(1); 
     int startIndex = 0; 
     int endIndex = RECURRSION_DEPTH; 

     while (endIndex > startIndex) { 

      fib(aValue,bValue,startIndex,endIndex); 

      aValue = fval[endIndex-2]; 
      bValue = fval[endIndex-1]; 
      startIndex = endIndex; 
      endIndex = Math.min(endIndex + RECURRSION_DEPTH, index); 
     } 

     System.out.println(Arrays.toString(fval)); 
    } 

    //use BigInteger to avoid integer max value limitation 
    public static void fib(BigInteger a, BigInteger b, int index, int endIndex) { 

     if (index >= endIndex) { 

      return ; 
     } 

     fval[index] = a.add(b); 
     index++; 
     fib(b, a.add(b), index , endIndex); 
    } 
} 

これは、サイズをスタックに関連しない、他の制限を有します。