java.lang.StackOverflowError en raison de la récursivité

Mon problème est que j'ai l'habitude de les obtenir un java.lang.StackOverflowError lorsque j'utilise la récursivité.
Ma question est, pourquoi ne récursivité cause stackoverflow autant plus que les boucles ne, et est-il un bon moyen d'utiliser la récursivité pour éviter un débordement de pile?

C'est une tentative de résoudre problème 107, il fonctionne bien pour leur exemple, mais à court d'espace de pile pour le problème lui-même.

//-1 16 12 21 -1 -1 -1 16 -1 -1 17 20 -1 -1 12 -1 -1 28 -1 31 -1 21 17 28 -1 18 19 23 -1 20 -1 18 -1 -1 11 -1 -1 31 19 -1 -1 27 -1 -1 -1 23 11 27 -1
public class tries
{
public static int n=7,min=Integer.MAX_VALUE;
public static boolean[][] wasHere=new boolean[n][60000];
public static void main(String[] args)
{
int[] lines=new int[n]; Arrays.fill(lines, -1000); lines[0]=0;
int[][] networkMatrix=new int[n][n];
Scanner reader=new Scanner(System.in);
int sum=0;
for(int k=0; k<n; k++)
{
for(int r=0; r<n; r++)
{
networkMatrix[k][r]=reader.nextInt();
if(networkMatrix[k][r]!=-1) sum+=networkMatrix[k][r];
Arrays.fill(wasHere[k], false);
}
}
recursive(lines,networkMatrix,0,0);
System.out.println((sum/2)-min);
}
public static void recursive(int[] lines, int[][] networkMatrix, int row,int lastRow)
{       
wasHere[row][value((int)use.sumArr(lines))]=true;
if(min<sum(lines)) return;
if(isAllNotMinus1000(lines)) min=sum(lines); 
int[][] copyOfMatrix=new int[n][n];
int[] copyOfLines;
for(int i=0; i<n; i++)
{
copyOfLines=Arrays.copyOf(lines, lines.length);
for(int k=0; k<n; k++)  copyOfMatrix[k]=Arrays.copyOf(networkMatrix[k], networkMatrix[k].length);
if(i!=0&&copyOfMatrix[i][row]!=0) copyOfLines[i]=copyOfMatrix[i][row];
copyOfMatrix[i][row]=0; copyOfMatrix[row][i]=0;
if(networkMatrix[row][i]==-1) continue;
if(wasHere[i][value((int)use.sumArr(copyOfLines))]) continue;
if(min<sum(copyOfLines)) continue;
recursive(copyOfLines,copyOfMatrix,i,row);
}
}
public static boolean isAllNotMinus1000(int[] lines)
{
for(int i=0; i<lines.length; i++) {if(lines[i]==-1000) return false;}
return true;
}
public static int value(int n)
{
if(n<0) return (60000+n);
return n;
}
public static int sum(int[] arr)
{
int sum=0;
for(int i=0; i<arr.length; i++) 
{
if(arr[i]==-1000) continue;
sum+=arr[i];
}
return sum;
}
}
Êtes-vous sûr que votre récurrences ne font pas appel à eux à l'infini? Il pourrait être utile d'inclure votre code.
le code est très compliqué, parce que cela fonctionne pour un petit nombre, je suis certaine que ce n'est pas le cas. En ajoutant le code est une bonne idée, peu importe, si. J'espère juste que ça ne serait pas de dérive trop de hors sujet.
Lorsque vous avez Entier.MAX_VALUE lignes, il a seulement fait la première de la récursivité de 7 dans chaque boucle un certain niveau n de profondeur, mais il a (7^(n+1)-1/6)-n-1 itérations pour aller, plus si les frapper de la base de cas. La route pour les boucles d'ajouter 6 fois n fois Entier.MAX_VALUE lignes.

OriginalL'auteur user2705335 | 2013-08-21

  1. 18

    pourquoi ne récursivité cause stackoverflow autant plus que les boucles ne

    Parce que chaque appel récursif utilisations de l'espace sur la pile. Si votre récursivité est trop profonde, il en résultera StackOverflow, selon la profondeur maximale autorisée dans la pile.

    Lors de l'utilisation de la récursivité, vous devriez être très prudent et assurez-vous de fournir un cas de base. Une base de cas dans la récursivité est la condition à laquelle la récursivité se termine et que la pile commence à se détendre. C'est la raison majeure de la récursivité provoquant StackOverflow erreur. Si il ne trouve aucun cas de base, il ira dans une récursion infinie, ce qui se traduira certainement par erreur, comme Stack est finie.

    OriginalL'auteur Rohit Jain

  2. 3

    Chaque appel récursif utilisations de l'espace sur la pile (à la maison quelque chose de spécifique à un appel, comme arguments, les variables locales, etc.). Ainsi, si vous faites trop d'appels récursifs (par pas correctement en fournissant une base de cas ou tout simplement en essayant de faire trop d'appels récursifs), alors il n'y a pas assez de place pour fournir de l'espace pour tout cela, et vous vous retrouvez avec un StackOverflow.

    La raison pour laquelle les boucles n'ont pas ce problème, c'est que à chaque itération d'une boucle de ne pas utiliser son propre espace (c'est à dire si je boucle n fois, je n'ai pas besoin d'espace supplémentaire pour faire le n+1st boucle).

    OriginalL'auteur Dennis Meng

  3. 3

    Dans la plupart des cas, un débordement de pile se produit car une méthode itérative a été mal défini, avec une inexistante ou inaccessible fin de la condition, ce qui provoque la pile de la mémoire de l'espace à être épuisé. Correctement écrit la récursivité ne devrait pas provoquer un débordement de pile.

    Cependant, il existe des situations où un méthode peut produire un débordement de pile même si elle a été correctement mis en œuvre. Par exemple:

    • Une croissance rapide (par exemple, exponentielle) de la récursivité. Par exemple: les naïfs récursive de la mise en œuvre de la fonction de Fibonacci
    • Une très grande entrée de données, qui finira par provoquer l'espace de pile à être épuisé

    Bas de ligne: tout dépend du cas particulier, il est impossible de généraliser concernant ce qui provoque un débordement de pile.

    OriginalL'auteur Óscar López

  4. 1

    Chaque fois que vous appelez une méthode, vous consommez un "cadre" de la pile, ce cadre n'est pas libéré jusqu'à ce que le retour de la méthode, il ne se passe pas la même chose avec des boucles.

    OriginalL'auteur morgano

  5. 0

    Lorsqu'elle est utilisée correctement, la récursivité ne produira pas une StackOverflowError. Si c'est le cas, votre base de cas n'est pas déclenché, et la méthode continue d'appeler lui-même à l'infini. Chaque appel de méthode qui ne se termine pas en reste sur la pile, et finalement, il déborde.

    Mais les boucles ne concernent pas les appels de méthode par eux-mêmes, de sorte que rien ne s'accumule sur la pile et un StackOverflowError ne donne pas de résultat.

    Vous êtes dans l'erreur. Certains lourde récursive méthodes nécessite de faire beaucoup de travail, il n'est pas signe de non-utilisation.

    OriginalL'auteur rgettman

  6. 0

    la récursivité provoque un débordement de pile, tous les appels sont en mémoire. si votre méthode s'appelle elle-même avec de nouveaux paramètres, puis qui appelle de nouveau lui-même. donc, tous ces appels pile généralement peuvent manquer de mémoire.
    boucles de stocker les résultats normalement dans certaines variables et appeler les méthodes qui est comme un nouveau appel à la méthode, après chaque appel, l'appelant méthodes se termine et renvoie les résultats.

    OriginalL'auteur Ashish Thukral

  7. 0

    La raison pour laquelle la récursivité provoque un débordement de pile est parce que nous ne parvenons pas à établir lors de la récursivité devrait s'arrêter, et donc la fonction/méthode de continuer à appeler lui-même "pour toujours" (jusqu'à ce qu'il provoque l'erreur). Vous aurez le même problème, même si vous êtes en utilisant des boucles, si vous avez quelque chose que les suivantes:

    bool flag = true;
while (flag == true){
count++;
}

    Depuis flag sera toujours vraie, la boucle while ne sera jamais s'arrêter jusqu'à ce qu'il vous donne l'erreur de dépassement de pile.

    Ce qui est faux. Ce que vous avez ici est une boucle infinie qui va provoquer le comte à débordement (en supposant que c'est un entier/long) mais il n'y a aucune chance que cela va provoquer une StackOverflowError. En effet, les boucles infinies sont largement utilisés.

    OriginalL'auteur Anna

  8. 0

    Chaque niveau de récursion que vous allez vers le bas, vous ajouter des informations d'état pour l'exécution de la pile. Cette information est enregistrée dans un historique d'activation et contient des informations comme les variables qui sont dans l'étendue et les valeurs qu'elles sont. Les boucles n'ont pas d'activation supplémentaire chaque fois que vous en boucle de sorte qu'ils prennent moins de mémoire.

    Dans certaines situations, votre la récursivité peut aller assez profond pour qu'il provoque la pile à débordement, mais il existe des moyens pour aider à empêcher que cela se produise. Lorsque vous travaillez avec la récursivité, j'ai l'habitude de suivre ce format:

    public obj MyMethod(string params) {
if (base-case) {
do something...
} else {
do something else...
obj result = MyMethod(parameters here);
do something else if needed..
}
}

    La récursivité peut être super efficace et faire des choses que les boucles ne peuvent pas. Parfois, vous arrivez à un point où la récursivité est le choix évident. Ce qui fait de vous un bon programmeur est d'être capable de l'utiliser quand il n'est pas complètement obvoius.

    OriginalL'auteur TJS