Discussion :

[beegees]

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 :

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

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 :

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

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

[souviron34]

Code :

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

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.

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 ??????

[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

@+

beegees

[Jedai]

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

Tu n'as pas l'air pourtant....
-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ï

[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 :

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

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

Tu n'as pas l'air pourtant....
-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.

-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

ici :

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

Merci encore à vous deux.

beegees

[souviron34]

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

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

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

[Jedai]

Code :

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

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ï

[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 :

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

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