Stack_Overflow_website_logo

Just kidding 😉

Lors de boucles récursives, passé un certain nombre d’appels il est fréquent de tomber sur une StackOverflowException (en fonction de la taille de votre pile).
Je suis tombé sur ce cas aujourd’hui alors voici comment il est, dans certains cas, possible de contourner le problème et de s’abstraire de la récursion.

Voici une boucle récursive :

/**
* Browse positions in order to find "great places";
* @param position Starting position
* @param greatPlaces Initial list of "great places"
* @return List of great places
*/
public static List<Position> process(Position current, List<Position> greatPlaces){

 if(current.isGreat()){
  greatPlaces.add(current);
  process(nextPosition(current), greatPlaces);
 }

 return greatPlaces;
}

Et voici comment, tout simplement, contourner cette récursion en la remplacent par un boucle associée à une pile (comme par hasard) :

/**
* Browse positions in order to find "great places";
* @param current Starting position
* @return List of great places
*/
public static List<Position> process(Position position){

 List<Position> greatPlaces = new ArrayList<Position>();
 Stack<Position> stack = new Stack<Position>();
 stack.push(position);

 while (!stack.isEmpty()) {
  Position current = stack.pop();
  if(current.isGreat()){
   greatPlaces.add(current);
   stack.push(nextPosition(current));
  }
 }

 return greatPlaces;
}
Publicités