cours  |  td  |  examens  |  doc  |  liens  |  horaires
 Scheme





PROGRAMMER DES BOUCLES :

LA RÉCURSION





  • 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

    
    
    trace (fact 4)
    
    
    
    (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 :
  • 
    
     

      U0 = 1

      U1 = 1

      UN = UN-1 + UN-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:

    trace (u 4)

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

    trace (pgcd 12 8)

    
    
    

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

     

      W1 = 1

      WN =  N  * WN-1   SI N PAIR 
              N+1

      WN = N+1 * WN-1   SINON
                N

     

    
    
    ÇA MARCHE :
    
    
      W2 = 2 * W1 = 2
              3             3
    
    
      W3 = 4 * W2 = 2 * 4
              3             3 * 3

    
    
      W4 = 4 * W3 = 2 * 4 * 4
              5             3 * 3 * 5
    
    
    ETC...
    
    
    
  • Exemple Wallis (programme : wallis.drs)
    
    
    
    
    

cours  |  td  |  examens  |  doc  |  liens  |  horaires
 Scheme