fonction récursive un peu lente

Je voudrais pas paraître impoli, mais je dois y aller.

Bonne nuit à tous:king:

PGZ

re bonjour,

puisque le voile est levé, voici la plus rapide :

Code:

---

1 2 3 4 5 6 7 8 9 10

'avec alVals(0 To 50) As Long Public Function fibo1(ByVal n As Long, ByRef alVals() As Long) As Long If n > 1 Then If alVals(n - 1) = 0 Then alVals(n - 1) = fibo1(n - 1, alVals) fibo1 = alVals(n - 2) + alVals(n - 1) ElseIf n = 1 Then fibo1 = 1 End If End Function

---

Philippe

plus rapide que quoi ?

Même si la question n'a que peu d'intérêt pratique, elle révèle de bons excercices techniques. Et cela vaut peut-être le coup de récapituler la discussion.
On veut calculer F(n) sachant que F(0) = 0; F(1) = 1 et F(n) = F(n-1) + F(n-2)
Les temps donnés ont été mesurés sur une machine de base et pour le calcul de F(30)

1. Méthode récursive évidente8-)

Code:

---

1 2 3 4 5 6 7 8 9 10

Function FiboRecLente(ByVal n As Integer) As Long   If n = 0 Then FiboRecLente = 0 ElseIf n = 1 Then FiboRecLente = 1 Else FiboRecLente = FiboRecLente(n - 1) + FiboRecLente(n - 2) End If End Function

---

Temps d'exécution : 800 000 µs

2. Méthode récursive rapide, genre casse-tête8O:aie:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Public Function FastFibonacci(n As Long) As Long FastFibonacci = FiboRec(0, 1, n) End Function   Private Function FiboRec(a As Long, b As Long, n As Long) As Long If n = 0 Then FiboRec = a Else FiboRec = FiboRec(b, a + b, n - 1) End If End Function

---

Temps d'exécution : 14 µs

3. Méthode itérative, facile.8-)

Code:

---

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

Function fctFiboIter(ByVal n As Integer) As Long Dim FnMoins1 As Long, FnMoins2 As Long, i As Integer   FnMoins2 = 0 FnMoins1 = 1 fctFiboIter = n   For i = 2 To n fctFiboIter = FnMoins1 + FnMoins2 FnMoins2 = FnMoins1 FnMoins1 = fctFiboIter Next i   End Function

---

Temps d'exécution : 4 µs.

4. Calcul direct de Maxence Hubiche:D

Code:

---

1 2 3

Function fiboForm(n As Long) As Long fiboForm = 1 / Sqr(5) * (((1 + Sqr(5)) / 2) ^ n - ((1 - Sqr(5)) / 2) ^ n) End Function

---

Temps d'exécution : 1,7 µs. La plus rapide, sauf pour les petites petites valeurs de n.

Les autres propositions semblent apparentées à celles-ci.

Pour Shaku une version débugage de l'itérative;) :

Code:

---

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

Function fctFiboIter(ByVal n As Integer) As Long Dim FnMoins1 As Long, FnMoins2 As Long, i As Integer   FnMoins2 = 0 FnMoins1 = 1 fctFiboIter = n Debug.Print "Init : Fibo = " & fctFiboIter & "; FN-1 = " & FnMoins1 & "; FN-2 = " & FnMoins2 & "; Pour n = " & n   For i = 2 To n fctFiboIter = FnMoins1 + FnMoins2 FnMoins2 = FnMoins1 FnMoins1 = fctFiboIter Debug.Print "Fin traitement i = " & i & " : Fibo = " & fctFiboIter & "; FN-1 = " & FnMoins1 & "; FN-2 = " & FnMoins2 Next i   End Function

---

PGZ

Bonjour,

Citation:

---

4. Calcul direct de Maxence Hubiche

---

Comment diable Maxence a-t'il pondu une pareille solution. ? :scarymov:

bonjour Maxence,

Citation:

---

plus rapide que quoi ?

---

Plus rapide en récursif car la plus rapide semble t'il est :

Code:

---

1 2 3 4

Private Function fibo99(ByVal n As Long) As Long fibo99 = ((1 + Sqr(5)) / 2) ^ n / Sqr(5) End Function

---

Philippe

Citation:

---

Envoyé par pgz

Salut Shaku.

C'est exactement le même problème qu'hier.
PGZ

---

je viens de suivre ce fil (impressionant 8O)c'est quoi celui d'hier (ya pas les dates sur le forum:()
Merci
PS j'ajoute
la séquence de Fibonacci est facilement solvable sur une feuille de calcul en tirant lune simple addition vers le bas, non ?

Bonjour.

Pour Daranc:

Citation:

---

c'est quoi celui d'hier

---

Reponse : améliorer une fonction récursive

Citation:

---

ya pas les dates sur le forum

---

Il y a date et heure du dernier post.

Citation:

---

Fibonacci est facilement solvable sur une feuille de calcul en tirant lune simple addition vers le bas, non ?

---

Oui.

Bonne journée,

PGZ

Merci:king:

Citation:

---

Envoyé par philben

bonjour Maxence,



Plus rapide en récursif car la plus rapide semble t'il est :

Code:

---

1 2 3 4

Private Function fibo99(ByVal n As Long) As Long fibo99 = ((1 + Sqr(5)) / 2) ^ n / Sqr(5) End Function

---

Philippe

---

:bravo: