StackOverFlow Exception dans les appels de récursion

Question

Im essayant un bit Et programme pour la plage de nombre entre a et b. Peut avoir 'n' testcases pour cela.
0<=a,b<=2^32
1<=n<=200

EXPLICATION:
1
2 4
calcul : 2&3&4

ENTREE:
1
4009754624 4026531839

SORTIE:
Exception in thread "main" java.lang.StackOverflowError at Example.BitwiseAnd.calculate(BitwiseAnd.java:78)

CODE:

public class BitwiseAnd 
{ 
    static long temp = 0; 
    static long result[]; 

    public static void main(String[] args) 
    { 
     Scanner scan = new Scanner(System.in); 
     int time = scan.nextInt(); 
     if(validateTime(time)) 
     { 
      result = new long[time]; 
      for(int i=0;i<time;i++) 
      { 
       long arr[] = new long[2]; 
       arr[0] = scan.nextLong(); 
       temp=arr[0]; 
       arr[1] = scan.nextLong(); 
       if(validateNum(arr[0],arr[1])) 
       { 
        result[i] = calculateUsingRecursion(arr[0],arr[1]); 
        //result[i] = calculateUsingForLoop(arr[0],arr[1]); 
       } 
       else 
       { 
        System.out.println("Enter a valid numbers"); 
       } 
      } 
      printResult(result); 
     } 
     else 
     { 
      System.out.println("Enter a valid number of testcases"); 
     } 
    } 

    public static void printResult(long[] result) 
    { 
     for(int i=0;i<result.length;i++) 
     { 
      System.out.println(result[i]); 
     } 
    } 

    public static boolean validateNum(long num1, long num2) 
    { 
     Long max = (long)Math.pow(2, 32); 
     if(num1<0 || num1>max) 
     { 
      return false; 
     } 
     else if(num2<0 || num2>max) 
     { 
      return false; 
     } 
     return true; 
    } 

    public static boolean validateTime(int time) 
    { 
     if(time<1 || time>200) 
     { 
      return false; 
     } 
     return true; 
    } 

    private static long calculateUsingRecursion(long num1, long num2) 
    { 
     while(num1<num2) 
     { 
      num1=num1+1; 
      temp=temp&num1; 
      calculateUsingRecursion(num1, num2); 
     } 
     return temp; 
    } 

    private static long calculateUsingForLoop(long num1,long num2) 
    { 
     num1=num1+1; 
     for(long i=num1 ; i<=num2 ; i++) 
     { 
      temp=temp&num1; 
     } 
     return temp; 
    } 
} 

le calcul de la méthode récursive me lancer StackOverflowException, pour un grand ensemble de nombres. Alors que la boucle pour fonctionne bien. Ma question ici est pourquoi ne pourrions-nous avoir la récursivité pour le grand ensemble d'entrées? Et comment cela pourrait-il être résolu avec la récursivité?

Answer 1

Vous n'avez pas ajouté toutes les infos (comme une pile complète) et il n'y a pas de méthode BitwiseAnd.calculate dans votre code.

1) Vous utilisez un "while" dans votre méthode de récurrence, mais vous ne devriez pas faire de boucle parce que c'est fait par l'appel récursif, vous devriez utiliser un "si" à la place.

2) La taille de la pile est limitée, donc une méthode ne peut pas s'appeler elle-même dans une boucle infinie. Et avec les entrées 4009754624 et 4026531839 il doit s'appeler 16777215 fois. Il y a plus de bélier nécessaire pour le fond. Mais pour le simplifier: Java doit allouer 2 longs arguments pour votre méthode 16777215 fois et il ne peut les réutiliser qu'après le retour de chaque méthode.

Donc, ne faites pas d'appels récursifs si vous faites beaucoup d'itérations.

Answer 2

Votre fonction récursive est en quelque sorte un mélange entre itératif et récursif. Modifier comme ceci:

private static long calculateUsingRecursion(long num1, long num2, long temp) { 

    // Stop condition 
    if (num1 >= num2) { 
     return temp; 
    }  

    // Progression 
    num1 = num1 + 1; 
    temp = temp & num1; 

    // Recursion 
    return calculateUsingRecursion(num1, num2, temp);   
} 

Notez que vous obtiendrez un StackOverflowException si une fonction récursive récursif trop profond.

Answer 3

Vous n'avez pas besoin de parcourir tous ces numéros. Vous avez juste besoin de trouver des bits qui sont constants pour tous les nombres dans l'intervalle (sinon leur ET est égal à zéro).

Passons en revue les bits du plus haut au plus bas et vérifions que a et b ont la même valeur de ce bit.Arrêtez l'itération quand ils ont des bits différents à une position:

long res = 0; 
for (int bit = 32; bit >= 0; --bit) { 
    long bita = a & (1L << bit); 
    long bitb = b & (1L << bit); 
    if (bita != bitb) break; 
    res |= bita; 
} 

Runnable: https://ideone.com/pkrUtV