Discussion :

[yotta]

Bonjour à vous,

Voilà, c'est très simple. Je suis autodidacte 100%, si bien que mon vocabulaire technique est plus personnel que standard. Et je n'arrive pas à comprendre ces deux termes lorsque je les rencontrent dans de nombreuses explications, ce qui a tendance à m'agacer.
En fait, récursive je comprends, c'est itérative qui me dépasse.....

Si l'un d'entre vous a deux minutes à perdre pour m'éclairer, j'en serai ravis.

[Katachana]

Les fonctions récursives sont des fonctions dont le calcul nécessite d'invoquer la fonction elle-même. la fonction s'appelle elle-meme.

l'exemple classique est la suite de Fibonnacci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
long fib(unsigned long n) {
    if (n <= 1) {
        return n;
    } else {
        return fib(n-1)+fib(n-2);
    }
}

La fonction itérative, comme son nom l'indique, contient des itérations pour arriver au résultat final. (fonction avec des boucles par exemple for,foreach, while, etc..)

[adiGuba]

Salut,


A titre d'exemple (et sauf erreur), l'algo iteratif pour la suite de fibonacci correspond à ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
    static long fib_i(long n) {
         long a = 0;
         long b = 1;
         long result = n;
 
         for (long i=2; i<=n; i++) {
             result = a + b;
             a = b;
             b = result;
         }
         return result;
    }

En règle général la version iterative d'un algo est plus performant que son équivalent recursive, car on évite d'empiler un grand nombre d'appel inutilement. La suite de Fibonacci en est un parfait exemple car avec la version recursif on arrive vite à saturation (temps de calcul de plus en plus long, et au bout d'un moment carrément une StackOverFlowException)


a++

[Rei Ichido]

+1 sur les performances.

Par contre, si le cas Fibonnaci est simple à gérer en itératif, il y a beaucoup de cas qui se codent très vite en récursif, et mais sont pénibles et peu intuitifs en itératif. Et donc ensuite, c'est un choix entre lisibilité et facilité vs performance.

[yotta]

Merci Katachana, adiGuba et Rei Ichido.
J'apprécie la précision de vos réponse. Malheureusement voyez-vous, je suis de plusieurs années lumières loin d'être un matheux...
Mon niveau scolaire (qui est loin derrière moi aujourd'hui) c'est arrêté au Bac +2 en électrotechnique. Des suites, je sais en avoir étudié mais je n'ai plus aucun souvenir. Quelques transformé de Laplace, calculs différentiels, ça s'arrête là. Donc j'avoue avoir un peu paniqué en lisant fibonacci.... connais pas ?
Bref, ça ne m'a pas empêché de comprendre vos explications. Mais là où je décroche, et j'avoue que personnellement, il ne me serait jamais arrivé de l'écrire comme ça mais à quelle occasion la forme décrite par Katachana représente-elle un intérrèt ?

long fib(unsigned long n) {
if (n <= 1) {
return n;
}
else {
return fib(n-1)+fib(n-2);
}
}

[Nudger]

Bonsoir,

La suite de fibonaci est une suite numérique où chaque valeur est la somme des deux précédentes (en commençant par 0 et 1).
Ca donne ça:
f(0): 0
f(1): 1
f(2): 1
f(3): 2
f(4): 3
f(5): 5
f(6): 8
f(7): 13
f(8): 21
...

La formule mathématique est donc f(n)=f(n-1)+f(n-2)
C'est une formule récursive car l'exécution d'une fonction dépend d'une autre exécution de cette même fonction.

Et pour répondre à la question: rédiger un algorithme de fibonaci de manière itérative est compliqué et probablement moche et incompréhensible alors que la forme récursive est tout à fait lisible et compréhensible quand on connaît la règle.

[Drawingrom]

Mais là où je décroche, et j'avoue que personnellement, il ne me serait jamais arrivé de l'écrire comme ça mais à quelle occasion la forme décrite par Katachana représente-elle un intérrèt ?

Quand tu ne sais pas a priori combien de fois tu va faire ton traitement, comme pour une arborescence.

[yotta]

Un grand merci à vous. Je crois qu'une ampoule vient de s'allumer dans mon cerveau...
On apprend vraiment beaucoup de choses très intéressantes sur ce site. Bravo.