Récursion terminale et Java

Récursion terminale et Java - Java - Programmation

Marsh Posté le 15-11-2008 à 00:12:36    

Bonjour  
 
J'ai fait la méthode suivant (utilisant la récursivité finale)  
 

Code :
  1. private static void populate(List<CompteNode> listNodes, List<Integer> params) {
  3.         // Conditions d'arrêt :
  4.         if (listNodes == null || listNodes.size() == 0) {
  5.             return;
  6.         }
  7.         CompteNode node = listNodes.remove(0);
  8.         Collection<Integer> notUsedParams = diff(params, node.getUsedParameters());
  9.         CompteNode child;
  10.         if (node.isValid() && notUsedParams != null && notUsedParams.size() > 0) {
  11.             for (Integer value : notUsedParams) {
  12.                 child = new CompteNode(value);
  13.                 node.add(child, OperationIF.OPERATION_PLUS);
  14.                 listNodes.add(child);
  16.                 child = new CompteNode(value);
  17.                 node.add(child, OperationIF.OPERATION_MOINS);
  18.                 listNodes.add(child);
  20.                 child = new CompteNode(value);
  21.                 node.add(child, OperationIF.OPERATION_MULTI);
  22.                 listNodes.add(child);
  24.                 child = new CompteNode(value);
  25.                 node.add(child, OperationIF.OPERATION_DIV);
  26.                 listNodes.add(child);
  27.             }
  28.         }
  30.         // Boucle récursive finale
  31.         populate(listNodes, params);
  32.     }


 
Et pourtant, j'obtiens l'horrible erreur suivante prouvant que cela ne  
fonctionne pas.  :??:  

Code :
  1. Exception in thread "main" java.lang.StackOverflowError
  2. at java.util.ArrayList.get(ArrayList.java:322)
  3. at java.util.AbstractList$Itr.next(AbstractList.java:345)
  4. at org.laruche.utils.CollectionUtils.diff(CollectionUtils.java:113)
  5. at org.laruche.compte.AppCompte.populate(AppCompte.java:91)


 
Je voudrais, donc, comment convaincre Java de faire de la récursivité terminale.
En vous remerciant  :jap:

Message cité 1 fois
Reply

Marsh Posté le 15-11-2008 à 00:12:36   

Reply

Marsh Posté le 15-11-2008 à 00:20:19    

Il ne me semble pas que Java ait la moindre garantie de l'appliquer quand ça semble pourtant possible, tu va devoir te résoudre à boucler à la main (ce qui est trivial dans ton cas, tu remplace ton if initial par un while avec la condition inverse et tu met tout le code dans le while, tu peut éventuellement séparer le test de nullité).

Message cité 1 fois

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 15-11-2008 à 13:08:35    

casper78 a écrit :

Je voudrais, donc, comment convaincre Java de faire de la récursivité terminale.


Java (comme nombre de langages) n'optimise pas la récursivité terminale.

 

Tu ne peux pas demander à java d'optimiser des tail-recs.

0x90 a écrit :

Il ne me semble pas que Java ait la moindre garantie de l'appliquer quand ça semble pourtant possible


Non seulement il n'y a aucune garantie mais ce n'est à ma connaissance absolument jamais fait, en tout cas sur le runtime Sun.

 

Après dans d'autres langages il existe des compilos pouvant parfois le gérer (me semble que GCC le fait quand certaines optims sont activées, et LLVM en est capable) mais se reposer là dessus quand c'est pas imposé par le langage rend le code absolument non portable :o

 

Dans les langages non fonctionnels, j'en ai pas encore vu qui demandaient impérativement l'optimisation de tail-rec, et même dans les langages fonctionnels ou multiparadigmes à tendance fonctionnels c'est pas nécessairement impératif (e.g. la spec de Common Lisp ne demande pas à ce que les implés optimisent la tail rec, par contre les Revised Reports [les specs/standards scheme] imposent l'optimisation)


Message édité par masklinn le 15-11-2008 à 13:16:24

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed