améliorer une fonction récursive

Bonsoir , j'ai écrit une petite fonction vba , mais quand je la teste avec des valeurs moyennes , ça fait bugger mon pc car ma fonction n'est pas optimisée , la voici :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Function SuiteN(ByVal n As integer, ByVal x As Double) As Double 'Renvoie une valeur approchée de la racine de x If n = 0 Then SuiteN = x / 2 ElseIf n > 0 Then SuiteN = (SuiteN(n - 1, x) + x / SuiteN(n - 1, x)) / 2 Else SuiteN = -1 End If End Function

---

Ma 1ere question est : quelqu'un peut il m'indiquer précisément comment je peux tester la fonction pas à pas avec toutes les étapes , que puis je écrire comme petite procédure et dans quelle fenêtre puis je voir les étapes?

Ma seconde question : si je fais Newton(30;2) , ça bug car 30 est trop grand , qu'est ce que je dois améliorer ici svp , le nombre de récursions sur n ? avez vous un indice ? Je ne souhaite pas une réponse tte faite je veux chercher , donc si vous avez un indice je suis preneur .

Je vous remercie .

bonjour,

pour la première question, vous pouvez faire un debug pas à pas dans VBE en mettant un point d'arrêt dans le code (cliquer sur la marge à gauche de la ligne d'instruction désirée) puis F8 pour avancer pas à pas.

pour la seconde :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

Function SuiteN(ByVal n As Integer, ByVal x As Double) As Double 'Renvoie une valeur approchée de la racine de x Dim dVal As Double If n > 0 Then dVal = SuiteN(n - 1, x) SuiteN = (dVal + x / dVal) / 2 ElseIf n = 0 Then SuiteN = x / 2 Else SuiteN = -1 End If End Function

---

c'est à dire économiser pour conserver votre pouvoir de calcul :aie:

Philippe

je n'avais dit pas de réponse toute faite résultat j'ai rien compris et ça m'a pourri mon exercice , merci

je vois pas du tout en quoi on économise du calcul , quelqu'un a t'il une explication car des résultats tout faits ça me sert à rien !

C'est une méthode anglo-saxonne : Comprendre par l'exemple :aie:

Philippe

tu fais le lien entre une variable et la fonction n-1 , en quoi tu économises du calcul vu que tu fais tjs les calculs ...

en plus là ma fonction n'est plus récursive vu qu'elle ne s'appelle plus ce que je n'ai pas le droit de faire...

ok,

1) Vois-tu une différence de résultats entre les 2 fonctions quelque soit n et x ?

2) Vois-tu une différence de temps d'exécution entre les 2 fonctions avec n = 23 par exemple ?

Philippe

Hello.

Je crois que ton pb vient de

Code:

---

SuiteN = (SuiteN(n - 1, x) + x / SuiteN(n - 1, x)) / 2

---

A chaque appel récursif le contexte de la procédure d'appel est empilé. Si tu appelles 30 fois, cela empile 30 contextes. Très viable.
Par contre ici tu appelles 2 fois sur la même ligne ta fonction. DOnc la 1ère fois 2 empilements qui chacun en provoquent 2 autres, soit 4, qui en provoquent 2 autres, soit 8, ... soit au final de l'ordre de 2^n. Avec 30 cela commence à faire beaucoup. Donc ton erreur doit indiquer un débordement de pile ou de capa mémoire.
Le code de Philben résoud le problème. Et il est bien récursif puisqu'il s'appelle.

En espérant que cela t'aide,

PGZ

salut pgz , je comprends pas bien cette ligne :

Citation:

---

Par contre ici tu appelles 2 fois sur la même ligne ta fonction. DOnc la 1ère fois 2 empilements qui chacun en provoquent 2 autres, soit 4, qui en provoquent 2 autres, soit 8, ... soit au final de l'ordre de 2^n.

---

C'est juste une suite, on calcule la valeur de n à partir du n-1 et pas de tous les n-1 , pourrais tu préciser ce que c'est ici les 2 empilements qui en déclenchent 2 autres car je comprends bien la notion de récursivité mais là je ne vois pas trop ce que tu veux dire , merci .

Citation:

---

Par contre ici tu appelles 2 fois sur la même ligne ta fonction. DOnc la 1ère fois 2 empilements qui chacun en provoquent 2 autres, soit 4, qui en provoquent 2 autres, soit 8, ... soit au final de l'ordre de 2^n

---

pas tout à fait exact puisque le nombre d'appel est (2x2^n)-1 contre n+1 de l'autre.

pgz, je te laisse le soin d'expliquer, merci,

philippe

Je te propose une expérience, juste pour que tu puisses percevoir ce qui se passe en récursivité.
Supposons qu'on veuille calculer le double de la somme des n premiers entiers naturels. D'accord c'est idiot puisque on sait que c'est = n*(n+1).

Je peux écrire

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Function fctRec(n As Integer) As Integer   If n > 0 Then fctRec = 2*( n + fctRec(n - 1)) ElseIf n = 0 Then fctRec = 0 Else fctRec = -1 End If   End Function

---

Tu peux l'appeler avec

Code:

---

1 2	Sub subTestFctRec msgbox fctRec(4)

---

Tu mets un point d'arrêt sur fctRec = 2*(n+fctRec(n-1))
et tu regardes ce qui se passe. Tu peux par exemple compter les passages par le point d'arrêt avec n = 1

ENsuite tu fais pareil avec

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Function fctRec(n As Integer) As Integer   If n > 0 Then fctRec = 2*n+ fctRec(n - 1) + fctRec(n - 1) ElseIf n = 0 Then fctRec = 0 Else fctRec = -1 End If   End Function

---

ET compare le nombre de passage avec n=1.

SI ce n'est pas encore clair à ce moment, recommence avec

Code:

---

msgbox fctRec(5)

---

...

PGZ

j'ai bien vu qu'avec le second c'etait bcp plus long mais j'ai rien compris car avec f8 ya que le truc jaune qui se déplace et je sais absolument pas comment le programme fait son calcul , ya pas une méthode plus précise que f8 ? je me sers mal d'excel comment je pourrais voir le détail des calculs de la fonction ?

Si tu n'y arrives pas avec ce que je t'ai dit, tu peux essayer avec l'affichage debug, après avoir modifié les fonctions comme ceci

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Function fctRec(n As Integer) As Integer   debug.print "appel de fctRec avec n = " & n If n > 0 Then fctRec = 2*( n + fctRec(n - 1)) ElseIf n = 0 Then fctRec = 0 Else fctRec = -1 End If   End Function

---

et bien sûr

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

Function fctRec(n As Integer) As Integer   debug.print "appel de fctRec avec n = " & n   If n > 0 Then fctRec = 2*n+ fctRec(n - 1) + fctRec(n - 1) ElseIf n = 0 Then fctRec = 0 Else fctRec = -1 End If   End Function

---

N'oublie pas d'ouvrir la fenêtre d'exécution.

PGZ

comment on fait pour faire l'affichage debug ?

SOus éditeur visual basic, menu Affichage / fenêtre d'exécution. Ou Ctrl-G.
Tu travailles avec quelle version d'Excel?

PGZ

Je bosse avec la version 2003 , j'arrive à faire ce que tu as dit ça m'a l'air très intéressant.
alors pgz j'ai pris comme valeur n = 2 pour la version longue avec les 2 fonctions n-1 et j'ai ceci dans la fenetre de debug :

Citation:

---

appel de fctRec avec n = 2
appel de fctRec avec n = 1
appel de fctRec avec n = 0
appel de fctRec avec n = 0
appel de fctRec avec n = 1
appel de fctRec avec n = 0
appel de fctRec avec n = 0

---

à partir de la 4eme ligne je ne vois pas pq la fonction s'appelle avec les valeurs 0 , 1 , 0 et 0 ...

Quand tu entres dans la fonction, n=2. La tu appelles 2 fois f(n-1)
appel 1 de 1. là tu appelles 2 fois n'-1 = 0
appel 11 de 0 fin de récursivité
appel 12 de 0 fin de récursivité
appel 2 de 1. là tu appeles 2 fois n'-1 = 0
appel 21 de 0 fin de récursivité
appel 22 de 0 fin de récursivité.

Ce qui explique bien ce que tu obtiens en debug, non?

Tu vois, ou pas?

je sais pas ça reste flou , j'ai fait pas mal d'exo sur la récursivité sans aucun probleme mais là je suis un peu perdu , les fonctions s'évaluent une à la fois ou se calcule une à la fois ?

Tu as sous les yeux le déroulement en réel. Si tu ne comprends pas bien, c'est que tu n'as pas encore saisi la récursivité. Prends ton temps.
Recommence l'exercice en partant de n = 0. Si tu comprends bien ce qu'il se passe, recommence avec n = 1. Quand tu comprends bien, passe à n = 2...

Dans le calme, tu vas comprendre.

Bon courage,

PGZ

pgz sérieusement là je vois vraiment pas pourtant j'ai aucun soucis avec la récursivité , c'est mal expliqué cette saloperie de débuggage de excel , j'entre dans ma fonction avec 2 :

2*2 + f(1) + f(1)

ensuite j'y entre avec 1 :

2*2 + 2*1 + f(0) + f(0)

et vu que là n = 0 je sors de ma fonction , j'obtiens 6 , toi avec ton programme tu obtiens 8 tu n'as pas fait une erreur quelque part ? car le double de la somme des 2 1ers entiers c'est 6 et non 8...

Tu as raison. L'algorithme est faux. Je voulais te faire comprendre comment s'exécute une fonction récursive et je n'ai pas vu que l'algo était faux. Et cela te perturbe.

Alors on reprend. Au temps pour moi :
- on calcule la somme des n premiers
- la "bonne" procédure c'est

Code:

---

fctRec = n + fctRec(n-1)

---

- la procédure "démonstrative" du pb est

Code:

---

fctRec = n + 2*fctRec(n-1) - fctRec(n-1)

---

Voilà. tu reprends avec cela et plus rien ne devrait te gêner.

PGZ