Récursion ou boucle

Question

J'ai une méthode qui calcule des statistiques :

public void calculateAverage(int hour){

    if (hour != 20) {
        int data =0; 
        int times = 0;
        for (CallQueue cq : queues) {
            data += cq.getCallsByTime().get(hour);
            times++;
        }       
        averageData.add((double)data/times);
        calculateAverage(hour + 1);
    }

}

Maintenant, je suis très fier d'avoir créé une méthode récursive mais je sais que cela aurait pu être résolu avec une boucle.

Ma question est la suivante : est-il préférable de résoudre ce genre de problèmes de manière récursive ou avec une boucle ?

Answer 1

Récursion en général

En général, une récursion serait plus coûteuse, car la pile doit être modifiée avec des copies de variables pour chaque récursion de la fonction.

Un ensemble d'adresses et d'états doit être sauvegardé, afin que la procédure récursive puisse retour au bon état après cette course particulière.

L'itération serait préférable si possible. Récursion, lorsque l'itération ne suffit pas, ou qu'elle aboutit à un code beaucoup plus compliqué .

---

Maintenance du code

Du point de vue de la maintenance, le débogage du code itératif est beaucoup plus facile que celui des procédures récursives car il est relativement plus facile pour comprendre l'état d'une itération particulière, plutôt que de penser à une récursion particulière.

---

Votre code

La procédure s'appelle elle-même, mais chaque exécution n'a rien à voir avec les résultats de l'exécution précédente. Chaque exécution étant indépendante est généralement le plus gros indice, que la récursion là n'est peut-être pas nécessaire .

A mon avis, calculateAverage(hour + 1); devrait être déplacé en dehors de la fonction, car il serait également plus clair pour quelqu'un qui lit votre code que chaque appel est indépendant.

Answer 2

En Java, C et Python, la récursion est assez coûteuse par rapport à l'itération (en général) parce qu'elle requiert la allocation d'un nouveau cadre de pile . Dans certains compilateurs C, on peut utiliser un drapeau de compilation pour éliminer cette surcharge, ce qui transforme certains types de récurrence (en fait, certains types d'appels de queue) en sauts au lieu d'appels de fonction. ( source )

Answer 3

Pour ce problème particulier, il n'y a pas trop de différence de temps d'exécution. Personnellement, je préférerais utiliser l'itération, je pense que ce serait plus simple et plus facile à comprendre, mais chacun son truc je suppose.

maintenant, certaines fonctions récursives (comme les nombres récursifs de Fibonacci par exemple) devraient être réalisées par itération plutôt, simplement parce qu'elles peuvent avoir une croissance exponentielle.

En général, je n'utilise pas la récursion à moins que cela ne rende mon problème plus facile à comprendre.

Answer 4

Vous devriez examiner les circonstances du périmètre. Pour les grandes récursions, la pile peut déborder, c'est +1 pour les boucles.

Je ne suis pas sûr de savoir lequel fonctionne le plus vite, mais c'est relativement facile à mesurer, en prenant en compte le JIT et d'autres éléments.

L'aspect maintenance du code : il est beaucoup plus facile pour la plupart d'entre nous de comprendre et de corriger les boucles que la récursion. Le temps des développeurs est généralement plus important que des différences de performance mineures.

Answer 5

Il dépend du contexte . Par exemple, si j'ai un arbre de Composite (dans SWT) et que vous souhaitez les parcourir, le moyen le plus simple est d'utiliser la récursion comme ceci :

    private boolean checkControlParent(Composite comp) {
        boolean ret = false;
        if (comp != null) {
            if (this.equals(comp)) {
                ret = true;
            } else {
                ret = checkControlParent(comp.getParent());
            }
        }
        return ret;
    }

sinon, si les performances sont importantes, sachez que les appels récursifs sont plus lents dans la plupart des cas que les boucles simples en raison de la surcharge des appels de fonctions/méthodes.

L'essentiel est donc que si vous avez besoin d'itérer à travers des objets pour lesquels la récursion est une solution naturelle et que vous ne risquez pas d'avoir une StackOverflowError allez-y et utilisez la récursion. Sinon, vous serez probablement mieux avec une boucle.

Une dernière chose : les méthodes récursives ont parfois tendance à être plus difficiles à lire, à comprendre et à déboguer.