Un Algorithme récursif.
Fermé
nico
-
25 févr. 2010 à 00:44
Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 - 25 févr. 2010 à 01:46
Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 - 25 févr. 2010 à 01:46
A voir également:
- Un Algorithme récursif.
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Code ascii algorithme - Guide
- Tester un algorithme en ligne - Forum Programmation
- Grep récursif - Forum Programmation
1 réponse
Pacorabanix
Messages postés
3248
Date d'inscription
jeudi 23 août 2007
Statut
Membre
Dernière intervention
19 mai 2013
661
25 févr. 2010 à 01:46
25 févr. 2010 à 01:46
l'idée d'un algo récursif, c'est de pouvoir calculer le résultat d'une fonction en rappelant la fonction elle-même avec un cas plus simple.
il faut aussi bien comprendre qu'une fonction peut s'appeler elle-même, et le nouvel appel à la fonction est complètement indépendant de l'appel de base, c'est comme si on appelait une autre fonction.
Ex :
Pour une puissance, on sait que le cas le plus simple c'est x^1, qui doit simplement redonner x.
ensuite, on remarque une chose : si on doit calculer x^n, c'est comme faire x * x^(n-1).
Par exemple, pour calculer x^4 (appel de fonction numéro 1), il faut calculer x^3 et multiplier par x.
Donc on calcule x^3 (appel de fonction numéro 2). pour cela il faut calculer x^2 et multiplier par x.
Donc on calcule x^2 (appel de fonction numéro 3). pour cela il faut calculer x^1 et multiplier par x
Donc on calcule x^1 (appel de fonction numéro 4). Ah ! Mais c'est le cas de départ, ça fait x. On renvoie x à la fonction qui m'a appelée (c'est l'appel numéro 3).
l'appel numéro 3 va multiplier par x cette valeur et donc renvoyer x*x à l'appel numéro 2.
l'appel numéro 2 va multiplier par x ce résultat et renvoyer x*x*x à l'appel numéro 1.
L'appel numéro 1 va multiplier par x ce résultat et donc renvoyer x*x*x*x à la fonction qui a demandé à calculer x puissance 4.
je ne sais pas si j'ai été clair...
il faut aussi bien comprendre qu'une fonction peut s'appeler elle-même, et le nouvel appel à la fonction est complètement indépendant de l'appel de base, c'est comme si on appelait une autre fonction.
Ex :
Pour une puissance, on sait que le cas le plus simple c'est x^1, qui doit simplement redonner x.
ensuite, on remarque une chose : si on doit calculer x^n, c'est comme faire x * x^(n-1).
Par exemple, pour calculer x^4 (appel de fonction numéro 1), il faut calculer x^3 et multiplier par x.
Donc on calcule x^3 (appel de fonction numéro 2). pour cela il faut calculer x^2 et multiplier par x.
Donc on calcule x^2 (appel de fonction numéro 3). pour cela il faut calculer x^1 et multiplier par x
Donc on calcule x^1 (appel de fonction numéro 4). Ah ! Mais c'est le cas de départ, ça fait x. On renvoie x à la fonction qui m'a appelée (c'est l'appel numéro 3).
l'appel numéro 3 va multiplier par x cette valeur et donc renvoyer x*x à l'appel numéro 2.
l'appel numéro 2 va multiplier par x ce résultat et renvoyer x*x*x à l'appel numéro 1.
L'appel numéro 1 va multiplier par x ce résultat et donc renvoyer x*x*x*x à la fonction qui a demandé à calculer x puissance 4.
je ne sais pas si j'ai été clair...
