complément d'information sur la récursivité

Bonjour tout le monde,

Quelqu'un saurait-il svp m'expliquer la récursivité.

Je vous le dis tout de suite, j'ai vu les cours de dvp.com mais ça ne m'a pas beaucoup avancé.

Voici un exemple :

Code:

---

1 2 3 4 5 6 7 8 9

f(n) = 3 * f(n-1) + 2 f(0) = -2     f(4) = 3 * f(3) + 2 = 3 * -28 + 2 = -82 f(3) = 3 * f(2) + 2 = 3 * -10 + 2 = -28 f(2) = 3 * f(1) + 2 = 3 * -4 + 2 = -10 f(1) = 3 * f(0) + 2 = 3 * -2 + 2 = -4 f(0) = -2

---

Je me demande où on va chercher ce -28, idem pour le -10 et le -4.

Code:

---

1 2 3 4 5 6 7 8 9 10

FONCTION F(n); PARAMETRES n : ENTIER; [I] RETOUR ENTIER; DEBUT SI n > 0 ALORS RETOURNER 3 * f(n-1) + 2; SINON RETOURNER -2; FIN SI FIN

---

Merci d'avance pour votre aide.

beegees

Citation:

---

Envoyé par beegees

Code:

---

1 2 3 4 5 6 7 8 9

f(n) = 3 * f(n-1) + 2 f(0) = -2     f(4) = 3 * f(3) + 2 = 3 * -28 + 2 = -82 f(3) = 3 * f(2) + 2 = 3 * -10 + 2 = -28 f(2) = 3 * f(1) + 2 = 3 * -4 + 2 = -10 f(1) = 3 * f(0) + 2 = 3 * -2 + 2 = -4 f(0) = -2

---

Je me demande où on va chercher ce -28, idem pour le -10 et le -4.

---

8O

3* -10 = -30
-30 + 2 = -28

3* -4 = -12
-12 + 2 = -10

3*-2 = -6
-6 + 2 = -4

Si tu ne sais pas ça, euh!!! que fais-tu en programmation ??????

Bonjour,

Merci pour ta réponse.

-10, -4 et -2 se sont donc des paramètres qu'on reçoit et qui ont été inventés pour l'exercice ?

S'étais juste ça ma question, le calcul, je l'avais compris 8O

@+

beegees

Bonsoir,

la récursivité c'est lorsqu'une fonction se rappelle elle même (définition grossière).
Comme tu le vois dans l'exemple que tu proposes "f(n) = 3 * f(n-1) + 2", pour calculer f(n), il te faut connaître f(n-1), ... pour caculer f(1) il te faut connaître f(0). Donc il te faut calculer le terme précédent à chaque étape jusqu'à f(0).

La première chose à faire lorsque tu entres dans une fonction récursive, c'est le test d'arrêt (afin d'éviter de boucler infiniment).

Expliquons un peu l'algorithme que tu étudies :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

FONCTION F(n); PARAMETRES n : ENTIER; [i] RETOUR ENTIER; DEBUT SI n > 0 ALORS //Test d'arrêt : on continu s'il y a encore des termes, sinon on renvoie f(0) RETOURNER 3 * f(n-1) + 2; // On est pas encore à f(0), donc on fait le calcul en appelant f(n-1) et en effectuant le calcul. SINON RETOURNER -2; // On est à f(0), donc on en revoe sa valeur FIN SI FIN

---

Citation:

---

Envoyé par beegees

Bonjour,

Merci pour ta réponse.

-10, -4 et -2 se sont donc des paramètres qu'on reçoit et qui ont été inventés pour l'exercice ?

S'étais juste ça ma question, le calcul, je l'avais compris 8O

---

Tu n'as pas l'air pourtant.... :aie:
-10, -4 ou -2 ne sont pas des paramètres, ce sont les valeurs de f(2), f(1) et f(0), qui sont calculées par l'algorithme (sauf f(0) qui est effectivement une valeur codée en dur dans l'algorithme, ce qu'on appelle le cas de base de la récursion).

--
Jedaï

Citation:

---

Envoyé par ToTo13

Bonsoir,

la récursivité c'est lorsqu'une fonction se rappelle elle même (définition grossière).
Comme tu le vois dans l'exemple que tu proposes "f(n) = 3 * f(n-1) + 2", pour calculer f(n), il te faut connaître f(n-1), ... pour caculer f(1) il te faut connaître f(0). Donc il te faut calculer le terme précédent à chaque étape jusqu'à f(0).

La première chose à faire lorsque tu entres dans une fonction récursive, c'est le test d'arrêt (afin d'éviter de boucler infiniment).

Expliquons un peu l'algorithme que tu étudies :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

FONCTION F(n); PARAMETRES n : ENTIER; [i] RETOUR ENTIER; DEBUT SI n > 0 ALORS //Test d'arrêt : on continu s'il y a encore des termes, sinon on renvoie f(0) RETOURNER 3 * f(n-1) + 2; // On est pas encore à f(0), donc on fait le calcul en appelant f(n-1) et en effectuant le calcul. SINON RETOURNER -2; // On est à f(0), donc on en revoe sa valeur FIN SI FIN

---

---

Bonsoir Toto13 et merci pour ta réponse.

En fait je savais que s'est une fonction qui s'appelle mais ce que tu indiques est très intéressant, surtout quand tu me dis que la première chose à faire est de tester l'arrêt.

Merci aussi pour l'explication de l'alogirthme, je vais l'imprimer et le mettre de côté, merci encore.

beegees

Citation:

---

Envoyé par Jedai

Tu n'as pas l'air pourtant.... :aie:
-10, -4 ou -2 ne sont pas des paramètres, ce sont les valeurs de f(2), f(1) et f(0), qui sont calculées par l'algorithme (sauf f(0) qui est effectivement une valeur codée en dur dans l'algorithme, ce qu'on appelle le cas de base de la récursion).

--
Jedaï

---

Bonsoir Jedaï,

Merci pour ta réponse.

Citation:

---

-10, -4 ou -2 ne sont pas des paramètres, ce sont les valeurs de f(2), f(1) et f(0),

---

En effet, j'avais pas compris cela :oops:

ici :

Citation:

---

f(4) = 3 * f(3) + 2 = 3 * -28 + 2 = -82

---

Je me demande d'où vient le -28 ?

S'est codé en dur quand même ? non ?


qu'est-ce que je fais sur ce forum, je devrais plutôt aller sur le forum couture :mouarf:

Merci encore à vous deux.

beegees

Citation:

---

Envoyé par beegees

Je me demande d'où vient le -28 ?

S'est codé en dur quand même ? non ?

---

8O

mais non, cela explicite le terme de gauche pour montrer comment l'algorithme marche, c'est tout....

Citation:

---

Envoyé par beegees

Code:

---

f(4) = 3 * f(3) + 2 = 3 * -28 + 2 = -82

---

Je me demande d'où vient le -28 ?

S'est codé en dur quand même ? non ?

---

Non !!!!
D'après la formule de récurrence, on a : f(4) = 3 * f(3) + 2
On calcule alors f(3), et on le remplace par sa valeur dans l'expression de f(4), ça donne : f(4) = 3 * (-28) + 2

(-28) n'est pas codé en dur, c'est le résultat du calcul de f(3).

--
Jedaï

Citation:

---

Envoyé par Jedai

Non !!!!
D'après la formule de récurrence, on a : f(4) = 3 * f(3) + 2
On calcule alors f(3), et on le remplace par sa valeur dans l'expression de f(4), ça donne : f(4) = 3 * (-28) + 2

(-28) n'est pas codé en dur, c'est le résultat du calcul de f(3).

--
Jedaï

---

Merci pour vos réponses, je viens de m'apercevoir que -28 était le résultat de f(3) :pan:

Merci encore à vous deux pour vos réponses.

beegees