Qu'est-ce que la récurrence ?

Programmation Fonctionnelle I, Automne 2017 Cours n°5

http://deptinfo.unice.fr/~roy

1. Une méthode majeure de démonstration de théorèmes en maths !

n (n + 1)

Programmer
• Soit n ≥ 1 et S(n) = 1 + 2 + .... + n. Prouver que S(n) =
2

PREUVE. Par récurrence sur n ≥ 1. En deux temps :

par récurrence a) si n = 1, c'est évident : 1 = 1 (1 + 1) /2

b) montrons que si la propriété est vraie pour n-1, alors elle reste
vraie pour n. Or :
S(n) = S(n-1) + n
= (n-1)n/2 + n par hypothèse de récurrence
= n[(n-1)/2 + 1] = n(n+1)/2
1+2+3+4+5 d'où la récurrence ! CQFD
=
(1 + 2 + 3 + 4) + 5 N.B. Le coeur de la stratégie réside dans l'obtention d'une relation
PCPS, chap. 6 de récurrence reliant S(n) et S(n-1), ici : S(n) = S(n-1) + n
2

2. Une méthode majeure de construction d'objets mathématiques ! 3. Une méthode majeure de raisonnement en programmation !

• Un entier naturel est 0 ou bien le successeur d'un entier naturel. On • Soit n ≥ 1 et S(n) = 1 + 2 + .... + n. Programmer la fonction S.
génère ainsi les entiers sous la forme 0, S(0), S(S(0)), etc.
PROGRAMMATION. Par récurrence sur n ≥ 1. En deux temps :
• La dérivée nème d'une fonction est la dérivée de la dérivée (n-1)ème.
a) si n = 1, c'est évident : S(1) = 1
On calcule ainsi de proche en proche f, f', f'', f(3), etc.
b) montrons que si je sais calculer S(n-1), alors je sais calculer S(n).
• Un quadruplet s'obtient en prenant un couple (u,x) où u est un triplet. Mais ceci découle de la relation de récurrence S(n) = S(n-1) + n
d'où la programmation par récurrence ! CQFP
• Un ensemble à n éléments s'obtient en ajoutant un nouvel élément à
un ensemble à n-1 éléments.
(define (S n) ; n entier ≥ 1 > S(10)
(if (= n 1) 55
etc. Et oui, ce ne sont que des maths ! 1 > S(0)
(+ (S (- n 1)) n))) dans les choux !
Mais comme les maths sont le domaine premier
de la rigueur, ne nous en éloignons que si nous
avons de très très bonnes raisons de le faire ! • Bien entendu il était ici possible de résoudre la récurrence en
faisant des maths, pour obtenir S(n) = n(n+1)/2. Mais ceci est trop
3
difficile dans le cas général en programmation. 4
• Une fonction est récursive si elle est programmée par récurrence. Somme des carrés des entiers de [0,100] n
k2
(define (fac n) ; n entier ≥ 0
(if (= n 0) 0! = 1 • On généralise le problème : somme des carrés k=0
1 n! = n ⇥ (n 1)! si n > 0 des entiers de [0,n] avec n ≥ 0.
(* (fac (- n 1)) n)))

02 + 12 + 22 + · · · + n2 = 02 + 12 + 22 + · · · + (n 1)2 + n2
• Autrement dit, elle s'utilise elle-même dans sa définition !
HR
• Mécanique à deux temps :
- si n=0, je sais calculer n! puisque 0! = 1
(define (somme-carres n) ; n entier ≥ 0
- si n>0, je suppose que je sais calculer (n-1)! et j'en déduis le calcul (if (= n 0)
0
de n! hypothèse de (+ (somme-carres (- n 1)) (sqr n))))
récurrence HR
• Il est vital de prévoir un cas de base [souvent n=0] sur lequel le cas
> (somme-carres 100)
général doit finir par converger. Erreur typique : 338350

(define (fac n) > (somme-carres -100)

(* n (fac (- n 1)))) n⇥ ⇤ User break
5 6

• Dans la fonction somme-carrés, le cas de base n = 0 n'est pas fameux La fonction puissance (expt x n) avec n entier ≥ 0 VERSION 1
car il restreint le domaine de définition de la fonction à N. En fait, il ne
• La fonction primitive (expt a b) calcule ab.
respecte pas la spécification mathématique de la fonction :
n • Comment programmerions-nous (expt x n) avec n entier ≥ 0 si elle
S(n) = k =
2
k 2
n'existait pas ? Nommons-la $expt pour ne pas tuer la primitive !
k=0 0 k n
x0 = 1
• Or pour n < 0, l'inéquation 0 ≤ k ≤ n n'a aucune solution, donc :
xn = x xn 1
si n > 0
S(n) = k =0
2
si n < 0
k ⇥ (define ($expt x n) ; x complexe, n entier ≥ 0
(if (= n 0)
1
(define (somme-carres n) ; n entier quelconque
(* x ($expt x (- n 1)))))
(if (<= n 0)
0
(+ (somme-carres (- n 1)) (sqr n))))
> ($expt 2 10)
1024

> (somme-carres 100) > (somme-carres -100)

338350 0
• Complexité : le nombre de multiplications est d'ordre n : en O(n).
7 8
La fonction puissance (expt x n) avec n entier ≥ 0 VERSION 2
Les ordres de grandeur en complexité
• Pour faire baisser la complexité, on essaye une DICHOTOMIE sur n.
• Lorsqu'on analyse la complexité d'un algorithme :
0
x = 1 - On choisit une unité de mesure. Par exemple le nombre
xn = (x )2 n/2
si n est pair d'opérations, ou le temps de calcul, ou l'espace mémoire consommé...
xn = x ⇥ (x2 )(n 1)/2
si n est impair - On se place toujours dans le pire des cas. Tel algorithme sera
rapide pour certaines données, et lent pour d'autres.
DICHOTOMIE : action de couper en deux !
• Si l'on s'intéresse au temps de calcul, on utilise la primitive time :

(define ($expt x n) ; x complexe, n entier ≥ 0 > (time (sqrt 67567563257846384730958398509836578365894534534509823))

(cond ((= n 0) 1) cpu time: 0 real time: 0 gc time: 0
((even? n) (sqr ($expt x (quotient n 2)))) 2.5993761416510383e+26
(else (* x (sqr ($expt x (quotient n 2))))))) (define (fac n) ;n≥0
> (time (* 0 (fac 5000))) (if (= n 0)
cpu time: 154 real time: 156 gc time: 112 1
• Complexité : le nombre de multiplications est d'ordre le nombre de 0 (* n (fac (- n 1)))))
fois que l'on peut diviser n par 2 avant de tomber sur 0. 154 - 112 = 42 ms
• C'est donc le logarithme en base 2 de n. Complexité O(log n). 9 gc = temps passé à nettoyer la mémoire [Garbage Collector] 10

• ATTENTION : le nombre d'opérations n'est pas nécessairement • Les grandes CLASSES DE COMPLEXITE [ coût] d'algorithmes :
proportionnel au temps de calcul ! En effet, multiplier des nombres à 3 - Les algorithmes de coût constant O(1). Leur complexité ne dépend pas de
chiffres ou à 300 chiffres ?... Exemple avec la factorielle : la taille n des données.
> (time (* 0 (fac 5000))) - Les algorithmes de coût logarithmique O(log n). Leur complexité est dans
cpu time: 154 real time: 155 gc time: 111
N = 5000 Temps = 43 le pire des cas de l'ordre de log(n).
0
> (time (* 0 (fac 10000))) - Les algorithmes de coût linéaire O(n). Leur complexité est dans le pire
N = 10000 Temps = 173
cpu time: 528 real time: 532 gc time: 355 des cas de l'ordre de n.
0
- Les algorithmes de coût quasi-linéaire O(n log n). Presqu'aussi bons que
• La complexité du calcul de (fac n) si l'on mesure le nombre de les algorithmes linéaires...
multiplications, est linéaire : d'ordre n. - Les algorithmes de coût quadratique O(n2). Pas fameux...

• La complexité du calcul de (fac n) si l'on mesure le temps de calcul - Les algorithmes de coût exponentiel O(2n). Catastrophique !!

n'est pas linéaire. Sinon, le temps de calcul pour N = 10000 aurait été
O(1) O(log n) O(n) O(n log n) O(n2) O(2n)
le double de celui pour N = 5000. Or c'est 4 fois plus !
n T=10 ms T=10 ms T=10 ms T=10 ms T=10 ms T=10 ms
Cela semble indiquer un comportement peut-être
quadratique en temps de calcul : en O(n2) ? PCPS exo 6.8.12 2n T=10 ms T+ε=10.5 ms 2T=20 ms 2T+ε=22 ms 4T=40 ms T2=100 ms
11 12
Résolution du problème combinatoire nb-régions Peut-on résoudre une récurrence ?
• Etant données n droites du plan en position générale, calculer le •Etant donnée une formule de récurrence, peut-on éliminer la
nombre Rn de régions (bornées ou pas). récurrence ? Trouver une formule directe pour le terme général ?
5
a) Si n = 0, il est clair que R0 = 1 6 REPONSE : C'est difficile voire impossible en général ! On le peut dans
b) Supposons connu Rn 1 et introduisons une 1
7
certains cas très simples, par exemple pour nb-regions.
4
nème droite dans une configuration de n-1 droites. 2
On déroule la récurrence :
La nème droite va rajouter une région pour chaque 3 R0 = 1
R n = Rn 1 +n
droite de la configuration, plus une dernière pour R n = Rn R n = Rn +n
2 + (n 1) + n 1
la région non bornée, ok ?
R n = Rn 3 + (n 2) + (n 1) + n
Rn = Rn 1 + (n 1) + 1 = Rn 1+n ···
R n = R0 + 1 + 2 + · · · + n
(define (nb-regions-direct n)
En résumé : (define (nb-regions n) > (nb-regions 3) Rn = 1 + (1 + 2 + · · · + n) (quotient (+ (* n (+ n 1)) 2) 2))
(if (= n 0) 7 n(n + 1)
1
Rn = 1 + Complexité : O(1) opérations !
> (nb-regions 10) 2
(+ (nb-regions (- n 1)) n))) 56 n2 + n + 2
Rn =
2 formule que l'on peut ensuite... prouver par récurrence !
• La complexité est O(n) en le nombre d'opérations. 13 14

Calcul approché d'une intégrale Une récurrence double : la suite de Fibonacci 0, 1, 1, 2, 3, 5, 8, 13...

•Intégrale approchée d'une f0 = 0, f1 = 1, fn = fn 1 + fn 2 si n ≥ 2

fonction continue f sur [a,b],
avec la méthode de Riemann : (define (fib n)
(if (< n 2)
découpage de [a,b] en
n
rectangles de largeur h, où h (+ (fib (- n 1)) (fib (- n 2)))))

est petit, par exemple 0.01.

Les deux appels récursifs
• Le cas de base a lieu lorsque a > b.
> (time (fib 15))
• La relation de Chasles permet un calcul récursif : cpu time: 1 real time: 1 gc time: 0
Z b Z a+h Z b
610
> (time (fib 30))
f (x)dx = f (x)dx + f (x)dx cpu time: 920 real time: 941 gc time: 0
a a a+h 832040
cf
Z b Z b T P
!
f (x)dx ⇡ h ⇥ f (a) + f (x)dx Oups !...
a a+h 15 16
• Oups ?... Regardons l'arbre du calcul : Résolution du problème combinatoire nb-chemins

(fib 30) • Parfois, ne pas hésiter à GENERALISER LE PROBLEME !

(fib 28) (fib 29) •Exemple : un robot parcourt un monde carré de B

côté N. Il doit se rendre du point A au point B en
N
(fib 26) (fib 27) (fib 27) (fib 28) suivant un chemin de longueur minimale 2N.
Combien de chemins possibles ? A
... ... ... ... ... ... ... ... N

1er ESSAI : Même si je suppose que je sais résoudre le problème dans

• L'algorithme passe son temps à faire et refaire les mêmes calculs !! un monde carré plus petit de côté N-1, je n'arrive pas à en déduire la
solution pour un monde carré de côté N. La récurrence brutale résiste !
•Le nombre de calculs est EXPONENTIEL puisque le nombre de noeuds
(define (nb-chemins N)
dans l'arbre est de l'ordre de 230. Très mauvais...
(if (= N 0)
1
• Nous aurons l'occasion de voir une autre solution plus rapide. (local [(define HR (nb-chemins (- N 1)))]
???)))
17 18

• Bloqué ! J'essaye de GENERALISER le problème. Le partionnement d’un entier p(8,3)

L
2ème ESSAI : Je vais donc relaxer les données B •Il s’agit d’un troisième exemple de 3 + 3 + 2
récurrence double (ou arborescente). 3 + 3 + 1 + 1 p(?,?)
et supposer que je travaille dans un rectangle 3 + 2 + 1 + 1 + 1
de largeur L et de hauteur H. H Etant donné deux entiers 0 ≤ m ≤ n, on note 3 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 2
D (partitions n m) le nombre de manières
•Pour aller de A vers B, je dois passer par C ou A
2 + 2 + 2 + 1 + 1 p(?,?)
C d’écrire n comme somme d’entiers ≤ m. ........
par D... et je me retrouve encore chaque fois Exemples : n=8, m=3 ci-contre.
dans un problème rectangulaire ! D'où la récurrence :
•Si je débute la somme par m, cela revient à partitionner ce qui reste
(define (nb-chemins-rect L H) ; monde rectangulaire m-n avec des entiers ≤ m.
(if (or (= L 0) (= H 0))
1 • Sinon cela revient à partitionner n avec des entiers ≤ m-1.
(+ (nb-chemins-rect (- L 1) H) ; en passant par C
• Attention aux cas de base !
(nb-chemins-rect L (- H 1))))) ; en passant par D

cf
> (partitions 5 5) > (partitions 15 15)

T
D
7 176
(define (nb-chemins N) ; le carré comme cas particulier

!
> (partitions 8 3) > (partitions 20 20)
(nb-chemins-rect N N)) 10 627

N.B. On peut ensuite localiser nb-chemins-rect à l'intérieur de nb-chemins. 19 20

Construction d'images par récurrence !

• Une image de n carrés emboîtés :

Méthodologie
•Lorsque vous êtes coincés [dans la vie, en maths, en programmation],
(define (carrés-emboîtés n size incr) ; récurrence sur n ≥ 1
(if (= n 1) essayez de PARLER, de VERBALISER...
(carré size)
(underlay (carré size) •Lors de la rédaction d'une fonction récursive f(n), n'hésitez pas à
(carrés-emboîtés (- n 1) (+ size incr) incr)))) DONNER UN NOM [par exemple HR] A L'HYPOTHESE DE
RECURRENCE :
> (carrés-emboîtés 5 30 20)
(define (fac n) ; n entier ≥ 0
(if (= n 0)
1
(local [(define HR (fac (- n 1)))] ; supposons que...
(* HR n))))

N.B. = ⊕
carré underlay
•Ceci est particulièrement vital si HR est utilisé plusieurs fois dans la
relation de récurrence (on ne calcule JAMAIS plusieurs fois HR !)...
Solution pour n Hypothèse de p
récurrence sur n-1 21
un = un 1 + un 1 Calcul naïf en O(2n) 22