Discussion :

[elodouwen]

salut à tous
voici mon petit programme :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (fibo-liste n) ;;; sort la liste des (n+3) premiers termes
  (cond 
     ((= n 1) (list 1))
     ((= n 2) (list 1 1))
     (else 
         (cons 
              (+ (car (fibo-liste (- n 1))) (car (fibo-liste (- n 2))))
              (fibo-liste (- n 1))
         )
      )
   )     
)

il est lent si je lui demande les 18 premiers termes
- j'appelle deux fois la fonction au rang n-1 ; est-ce une erreur stratégique ? cela ralentit-il les calculs ? comment optimiser le programme ?
- j'utilise Scheme dans Dr Racket ; est-ce une interface lente ? si je vise de gros calculs quel autre interface choisir, sachant aussi qu'à terme je veux faire des graphiques mathématiques animés sans limitation de puissance ou de lenteur
merci de vos éclairages

Vincent

[byjav]

Salut !

Tout d'abort, ta fonction n'est pas à récursivité terminale. Je suppose que la différence entre la réalisation naïve de la suite de Fibonacci et en une réalisation à récursivité terminale, qui correspond à une boucle, est traîtée dans chaque introduction à la programmation fonctionnelle. Ça doit être facile à trouver.

Ensuite, tu appelles la fonction trois fois, mais c'est en effet une erreur stratégique de l'appeller plus qu'une fois. Voici les appels:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
fibo-liste 1: retourne le résultat

fibo-liste 2: retourne le résultat

fibo-liste 3:
        fibo-liste 2
        fibo-liste 2
        fibo-liste 1

fibo-liste 4:
        fibo-liste 3
                fibo-liste 2
                fibo-liste 2
                fibo-liste 1
        fibo-liste 3
                fibo-liste 2
                fibo-liste 2
                fibo-liste 1
        fibo-liste 2

fibo-liste 5:
    fibo-liste 4:
            fibo-liste 3
                    fibo-liste 2
                    fibo-liste 2
                    fibo-liste 1
            fibo-liste 3
                    fibo-liste 2
                    fibo-liste 2
                    fibo-liste 1
            fibo-liste 2
    fibo-liste 4:
            fibo-liste 3
                    fibo-liste 2
                    fibo-liste 2
                    fibo-liste 1
            fibo-liste 3
                    fibo-liste 2
                    fibo-liste 2
                    fibo-liste 1
            fibo-liste 2
    fibo-liste 3:
            fibo-liste 2
            fibo-liste 2
            fibo-liste 1

Alors, le nombre des appels croît exponentiellement.

Mais dans ta fonction, c'est aussi les miettes qui croissent exponentiellement. En effet, dans chaque appel tu crées trois listes dont tu ne réutilises qu'une : alors, les deux autres deviennent miettes.

Je te recommande d'essayer d'écrire une telle fonction à récursivité terminale. On utilise des fonctions auxiliaires dont les arguments sont analogiques à des courseurs et des accumulateurs des boucles. Voici une réalisation avec « named let »:

Code :

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

1
2
3
4
5
6
7
8
9
(define (fibo-liste-tail n)
  (let bucle ((k 0)
             (acc '()))
    (if (<= n k)
        acc
        (let ((next (if (< k 2)
                        1
                        (next-fib (car acc) (cadr acc)))))
          (bucle (+ k 1) (cons next acc))))))