Cours 4 - La récursivité

name: inverse
layout: true
class: center, middle, inverse

---
# Inès de Courchelle
## La récursivité
## 2024-2025

![image](../img/CY-tech.png)

---
layout: false
# Plan
## Today
1. Définition
2. Fonction/Procédure récursive
3. Exemples

---
# Définition
## Principes
<img src="https://media.tenor.com/01wiYZ4-Ki8AAAAC/perfect-loop-the-simpsons.gif" width="200">

## En gros
.otro-blockquote[La récursivité c’est quand une fonction s’appelle elle-même jusqu’à atteindre une condition d’arrêt]

---
# La récursivité
## Définition
Algorithme permettant de résoudre un problème en calculant des solutions d'instances plus petites du même problème
## Principes
- Une fonction qui s'appelle elle même jusqu'à atteindre une condition d'arrêt
- Le résultat de chaque fonction enfant est retourné dans les fonctions parents, jusqu’à retourner à la fonction originale

## Pourquoi ?
- Pour gagner en temps d'execution
- Pour gagner en mémoire

---
# La récursivité
## Illustration
#### Le compte à rebours
On souhaite créer un Compte à rebours à partir de 10.

#### Etape 1
on affiche : 10

#### Etape 2
on affiche : 9

#### Etape 3
on affiche : 8

#### Etape ...
on afiche : 0

---
# Le Compte à rebours
## Avant
```c
PROCEDURE compteARebours(cpt : entier)
DEBUT
 FAIRE
 ECRIRE(cpt)
 cpt <- cpt - 1
 TANT QUE(cpt>0)
FIN
```
.underR[Il faut transformer ça en récursif]

#### Mais comment ?

---
# La récursivité
## Étapes
1. La condition d'arrêt
2. La résolution du problème
3. L'appel récursif

## Illustration
Afin d'illustrer la récursivité nous allons prendre l'exemple du compte à rebours.

---
# La récursivité
## Le compte à rebours
#### 1. La condition d'arrêt
Lorsque le compteur arrive à zéro
#### 2. La résolution du problème
compteur = compteur -1
#### 3. L'appel récursif
retourner le compteur

---
# La recursivité
## AVANT
```c
PROCEDURE compteARebours(cpt : entier)
DEBUT
 FAIRE
 ECRIRE(cpt)
 cpt <- cpt - 1
 TANT QUE(cpt>0)
FIN
```

## APRES
```c
PROCEDURE compteARebours (cpt : entier)
DEBUT
    SI cpt=0 FAIRE
        ECRIRE(CPT)
    SINON
        ECRIRE(cpt)
        compteARebours(cpt-1)
    FIN
FIN
```

---
# La recursivité
## L'algo
```c
PROCEDURE compteARebours (cpt : entier)
DEBUT
    SI cpt=0 FAIRE
        ECRIRE(CPT)
    SINON
        ECRIRE(cpt)
        compteARebours(cpt-1)
    FIN
FIN
```

## Le code
```c
void compteARebours (int cpt) {
  if (cpt==0)
    printf("%d \n",cpt);
  else {
    printf("%d \n",cpt);
    compteARebours(cpt-1);
  }
}
```
---
# La récursivité
## On peut aussi ...
- Faire une procédure récursive
- Faire une fonction récursive

## Algo
.pull-left[
```c
PROCEDURE compteARebours (cpt : entier)
DEBUT
    SI cpt=0 FAIRE
        ECRIRE(CPT)
    SINON
        ECRIRE(cpt)
        compteARebours(cpt-1)
    FIN
FIN
```

]
.pull-right[
```c
FONCTION compteARebours (cpt : entier): entier
  SI (cpt=0) FAIRE
    retourner 0
  SINON
    printf("%d \n",cpt)
    retourner compteARebours(cpt-1)
  FIN
FIN
```
]

---
# La recursivité
## L'algo
```c
FONCTION compteARebours (cpt : entier): entier
  SI (cpt=0) FAIRE
    retourner 0
  SINON
    printf("%d \n",cpt)
    retourner compteARebours(cpt-1)
  FIN
FIN
```
## Le code
```c
int compteARebours (int cpt) {
  if (cpt==0)
    return 0;
  else {
    printf("%d \n",cpt);
    return compteARebours(cpt-1);
  }
}
```

---
# La récursivité
## La var

<center>
<video src="videos/car.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

---
# La récursivité
## En gros
Un appel récursive remplace une boucle

## Illustration
.pull-left[
```c
PROCEDURE helloThere
DEBUT
 POUR i allant de 0 à 4 FAIRE
 ecrire("coucou')
 FIN POUR
FIN
```
]
.pull-right[
```c
PROCEDURE helloThere(i: entier)
DEBUT
 SI (i=0) ALORS
 ecrire ("coucou")
 SINON
 ecrire ("coucou")
 i <- i - 1
 helloThere(i)
 FIN SI
FIN
```
]
---
# La récursivité
## Terminale
.otro-blockquote[Une fonction avec une récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée. ]
## Non terminale
C'est l'inverse !

---
# La récursivité
## Terminale
```
FONCTION exempleT(n : entier) : entier
DEBUT
    SI condition d'arret FAIRE
        RETOURNER ...
    SINON
        RETOURNER exempleT(n-1)
FIN
```

## Non terminale
```
FONCTION exempleT(n : entier) : entier
DEBUT
    SI condition d'arret FAIRE
        RETOURNER ...
    SINON
        RETOURNER n+ exempleT(n-1)
FIN
```
---
# Autrement dit
## Composantes d’une fonction récursive
```c
f(x) = SI c(x)  alors
           g(x)
       SINON
           h(f(s(x)), x)
```
- c(x) est dite condition d’arrêt ;
- g(x) est le cas trivial, il peut retourner une valeur constante ;
- s(x) est la fonction “successeur” de x ;
- h(f(s(x)),x) est l’appel récursif, fonction de x et du successeur de x. Si h est la fonction identité, la récursivité est dite terminale; non terminale sinon.

---
# Autrement dit
## Terminale
- Tout appel récursif de f est de la forme return f(...)
- La valeur retournée est directement la valeur obtenue par un appel récursif, sans qu'il n'y ait aucune opération sur cette valeur
-Une fonction avec une récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée.

## Non terminale
C'est l'inverse !

---
# La récursivité
## Somme d'un tableau
On considère le tableau suivant :
<img src="img/monTab.png" width=300>

## Comment faire ?
1. Récursif non terminal
2. Récursif terminal

---
# La récursivité
## NON TER : Somme d'un tableau
<img src="img/monTab.png" width=300>

#### 1. La condition d'arrêt
Je suis à la fin de mon tableau

#### 2. La résolution du problème
somme = tab[i] + somme

#### 3. L'appel récursif
sommeTableau avec la case suivante i = i+1

---
# La récursivité
## NON TER : Somme d'un tableau
<img src="img/monTab.png" width=300>

#### 1. La condition d'arrêt
<img src="img/conditionArret.png" width=300>

---
# La récursivité
## NON TER : Somme d'un tableau
<img src="img/monTab.png" width=300>

#### 2. La résolution du problème
<img src="img/resolutionP.png" width=300>

---
# La récursivité
## NON TER : Somme d'un tableau
<img src="img/monTab.png" width=300>

#### 3. L'appel récursif
<img src="img/appelRec.png" width=300>

---
# La récursivité
## NON TER : Somme d'un tableau
#### ALGO
```c
FONCTION somme(i : entier, tab: tableau d'entiers) : entier
DEBUT
    SI (i=TAILLE) ALORS
        retourner 0
    SINON
        RETOURNER TAB[i] + somme(i+1,tab)
    FIN SI
FIN
```

---
# La récursivité
## NON TER : Somme d'un tableau
#### En C
```c
int somme(int i, int tab[TAILLE]){
  if(i==TAILLE){
    return 0;
  }
  else{
    return tab[i] + somme(i+1,tab);
  }
}
```
---
# La récursivité
## EN NON TERMINAL : Somme d'un tableau

<center>
<video src="videos/sommeNT.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

---
# La récursivité
## NON TER : Somme d'un tableau
#### EXPLICATION
<img src="img/explicationSommeT.png" width=800>

---
# La récursivité
## NON TER : Somme d'un tableau
#### EXPLICATION
<img src="img/explicationSommeT2.png" width=800>

---
# La récursivité
## EN TERMINAL : Somme d'un tableau
<img src="img/SommeTEREXP.png" width=700>

---
# La récursivité
## EN TERMINAL : Somme d'un tableau
<img src="img/SommeTEREXP2.png" width=600>

---
# La récursivité
## EN TERMINAL : Somme d'un tableau
```c
FONCTION somme(i : entier, tab: tableau d'entiers, acc :entier) : entier
DEBUT
 SI (i=TAILLE) ALORS
 retourner acc
 SINON
 RETOURNER somme(i+1,tab,acc+tab[i])
 FIN SI
FIN
```
---
# La récursivité
## EN TERMINAL : Somme d'un tableau
<img src="img/SommeTEREXP3.png" width=600>

---
# La récursivité
## EN TERMINAL : Somme d'un tableau
<img src="img/sommeTerminale.png" width=800>

---
# La récursivité
## EN TERMINAL : Somme d'un tableau

<center>
<video src="videos/sommeT.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

---
# La récursivité
## Des exemples Mathèmatiques
- Factorielle
- Fibonacci

---
# La récursivité
## Exemple : la factorielle
```
0! = 1
1! = 1
2! = 1 × 2 = 2
3! = 1 × 2 × 3 = 6
4! = 1 × 2 × 3 × 4 = 24
```

## Identifier
#### 1. La condition d'arrêt
#### 2. La résolution du problème
#### 3. L'appel récursif

---
# La récursivité
## La factorielle
#### En math
n!=n*(n-1)!
#### En gros !
 4! = 4 x 3! = 4 x (3 x 2!) = 4 x (3 x (2 x 1!)) = 4 x (3 x (2 x (1 x 0!)))
<img src="https://c.tenor.com/Cdl0FgZUZ6kAAAAd/doug-maclean-mac.gif" width="250">

---
# La récursivité
<img src="img/facto1.png" width="250">

---
# La récursivité
<img src="img/facto2.png" width="300">

---
# La récursivité
<img src="img/facto3.png" width="375">

---
# La récursivité
## La factorielle
```
FONCTION factorielle(n : entier) : entier
DEBUT
    SI n=0 ALORS
        RETOURNER 1
    SINON
        RETOURNER n * factorielle(n-1)
FIN
```
---
# La récursivité
## La factorielle

```
FONCTION factorielle(n : entier) : entier
DEBUT
 SI n=0 ALORS
 RETOURNER 1
 SINON
 RETOURNER n * factorielle(n-1)
FIN
```
<img src="img/factoEx1.png" width="450">