Scheme

PROGRAMMER DES BOUCLES :
LA RÉCURSION

"PROGRAMMER DES BOUCLES"
= INDIQUER À LA MACHINE
DE RÉPÉTER QUELQUE CHOSE
UN CERTAIN NOMBRE DE FOIS
--> STRUCTURE DE CONTRÔLE RÉPÉTITIVE

EN SCHEME, C'EST TRÈS SIMPLE...

... IL N'Y A PAS DE PRIMITIVE
POUR LE CONTRÔLE DE LA RÉPÉTITION !!!

BOUCLES SONORES :

ÉVÉNEMENT MIDI:
(<NOTE> <DATE> <DURÉE> <VÉLOCITÉ> <CANAL>)

FONCTIONS UTILISANT MZSHARE:

JOUER-MIDI --> JOUE UN EVENEMENT

JOUER-LISTE-AT
--> JOUE UNE LISTE D'EVENEMENTS A UNE DATE

MIDI-GET-TIME --> DATE COURANTE

PAUSE --> PAUSE PENDANT UNE DURÉE

(JOUER-POUM D)
= (JOUER-MIDI (LIST 36 D 250 80 9))
(JOUER-TCHI D)
= (JOUER-MIDI (LIST 42 D 250 80 9))

BPM = 120 ("BEATS PER MINUTE")
--> DURÉE DU BEAT = 500 MILLISECONDES


(DEFINE (BOUCLE D)

  (JOUER-POUM D)

  (JOUER-TCHI (+ D 250))

  (PAUSE 450)

  (BOUCLE (+ D 500)))

       ;APPEL RÉCURSIF

--> ON LANCE (BOUCLE (MIDI-GET-TIME))

PROBLÈME: BOUCLE INFINIE!!!!
(ARRÊT AVEC LE BOUTON "BREAK")

--> POUR CONTRÔLER L'ARRÊT D'UNE BOUCLE: IL FAUT UN "TEST D'ARRÊT"


(DEFINE (BOUCLE1 D N)

  (DISPLAY N) (NEWLINE)

  (JOUER-POUM D)

  (JOUER-TCHI (+ D 250))

  (PAUSE 450)

  (IF (= N 0) 'STOP    ;TEST D'ARRÊT

      (BOUCLE1 (+ D 500) (- N 1))))

       ;APPEL RÉCURSIF

--> ON LANCE (BOUCLE1 (MIDI-GET-TIME) 10)

AVEC UNE LISTE D'EVENEMENTS MIDI ?
EXEMPLE : "HOUSE"
--> DUREE TOTALE = 8000 MILLISECONDES
(JOUER-HOUSE D)
= (JOUER-LISTE-AT D HOUSE)


(DEFINE (BOUCLE2 D N)

  (DISPLAY N) (NEWLINE)

  (JOUER-HOUSE D)

  (PAUSE 7900)

  (IF (= N 0) 'STOP    ;TEST D'ARRÊT

      (BOUCLE2 (+ D 8000) (- N 1))))

       ;APPEL RÉCURSIF

--> LA SÉQUENCE "HOUSE" EST RÉPÉTÉE EN BOUCLE

Exemples de boucles sonores : poumtchi.mp3, house.mp3 (programme : midiboucle.drs)

APPEL RÉCURSIF ENCAPSULÉ : FACTORIEL

N! = 1 * 2 * 3 * ... * N

DÉFINITION MATHÉMATIQUE PAR RÉCURRENCE :

F(0) = 1
F(N) = N * F(N-1)

EN SCHEME, CELA S'ÉCRIT :


(DEFINE (F N)

  (COND ((= N 0) 1)

        (ELSE (* N (F (- N 1))))))

"COND" = STRUCTURE DE CONTRÔLE CONDITIONNELLE,
MAIS PAS DE PRIMITIVE SCHEME POUR LA RÉPÉTITION !!!

POURQUOI ÇA MARCHE ???
--> FAIRE UNE "TRACE":
= DÉTAILLER "À LA MAIN" LE CALCUL
POUR UNE PETITE VALEUR DE DÉPART


(DEFINE (F N)

  (COND ((= N 0) 1)  ; TEST D'ARRÊT

        (ELSE (* N (F (- N 1))))))

                 ; APPEL RÉCURSIF ENCAPSULÉ

UN "APPEL RÉCURSIF":
APPEL DE FONTION À L'INTÉRIEUR DE SA PROPRE DÉFINITION

POUR FAIRE UNE STRUCTURE RÉPÉTITIVE EN SCHEME:

SI "TEST D'ARRÊT" VRAI, ALORS STOP

SINON FAIRE UN CALCUL, AVEC UN "APPEL RÉCURSIF" (= RECOMMENCER) PORTANT SUR DES DONNÉES MODIFIÉES

"DONNÉE MODIFIÉE"
= À L'APPEL RÉCURSIF, N EST REMPLACÉ PAR N-1

FIBONACCI :

  U₀ = 1
  U₁ = 1
  U_N = U_N-1 + U_N-2


(DEFINE (U N)

  (COND ((= N 0) 1)

        ((= N 1) 1)   ; TESTS D'ARRÊT

        (ELSE (+ (U (- N 1)) (U (- N 2))))))

           ; APPELS RÉCURSIFS ENCAPSULÉS

UNE TRACE:

Exemple Fibonacci (programme : fibo.drs)

CALCUL DU PGCD : ALGORITHME D'EUCLIDE

  PGCD(A, B) = PGCD(B, A MOD B)
    OÙ A MOD B = RESTE DE LA DIVISION DE A PAR B ==> < B
  PGCD(A, 0) = A

A = BQ + R


(DEFINE (PGCD A B)

 (COND ((= B 0) A)

       (ELSE (PGCD B (REMAINDER A B)))))

UNE TRACE:

APPROXIMATION DE PI : FORMULE DE WALLIS

PI = 2 * 4 * 4 * 6 * 6 * 8 ...
4     3 * 3 * 5 * 5 * 7 * 7 ...

DÉFINITION MATHÉMATIQUE PAR
RÉCURRENCE ???

  W₁ = 1
  W_N = N * W_N-1   SI N PAIR
          N+1
  W_N = N+1 * W_N-1   SINON
            N

ÇA MARCHE :

  W₂ = 2 * W₁ = 2
          3             3

  W₃ = 4 * W₂ = 2 * 4
          3             3 * 3

  W₄ = 4 * W₃ = 2 * 4 * 4
          5             3 * 3 * 5

ETC...

Exemple Wallis (programme : wallis.drs)

Scheme

PROGRAMMER DES BOUCLES : LA RÉCURSION

BOUCLES SONORES :

APPEL RÉCURSIF ENCAPSULÉ : FACTORIEL

FIBONACCI :

CALCUL DU PGCD : ALGORITHME D'EUCLIDE

APPROXIMATION DE PI : FORMULE DE WALLIS

PROGRAMMER DES BOUCLES :
LA RÉCURSION