Comment implémenter la récursion de queue avec ma méthode Fibonacci?

Question

J'essaie de calculer de grands nombres de la séquence de Fibonacci, d'où la raison pour laquelle j'utilise un grand nombre entier. Je peux aller jusqu'à environ 10000 comme ça, mais je n'ai plus d'espace dans la pile. Je réalise que je peux augmenter l'espace de pile et de tas, mais je crois comprendre que la récursion de queue peut contourner le problème d'espace. Voici mon code ..

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

Ceci est ma mise en œuvre préférée de Fibonacci.

Il est récursif, mais s'exécute dans O (n), pas O (2^n). Maintenant, je ne suis pas sûr de vos besoins en matière de récursion de la queue, ou si cela peut vous aider. Aussi, vous devriez faire une réelle implémentation OO autour de cette logique.

Answer 2

Un récursivité simple à réaliser la série que vous voulez pourrait être:

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

Pour éviter les limitations de la pile, vous pouvez limiter la profondeur de récursivité et faire la résurrection en quelques « morceaux ». Voici un exemple d'une série de 50 éléments, calculée avec une profondeur limitée à 10 (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); 
    } 
} 

Bien sûr, cela n'a pas d'autres limitations, liées à la taille de la pile.