1. Réalisez une trace d'exécution de l'algorithme précédent avec $x=2$ et $n=3$. Est-ce que puissance_rec(2,3) renvoie bien $2^3$ ?

2. Recopiez le script précédent puis testez-le plusieurs fois, par exemple avec $x=2$ et $n=10$, s'interrogez si puissance_rec(2,10) renvoie bien $2^{10}$.

Repérer parmi les fonctions suivantes celles qui sont récursives :

fonction f1 :

def f1(n: int) -> int:
if n==0:
    return 0
else:
    return n-1
         

fonction f2 :

def f2(n: int) -> int:
if n==0:
    return 0
else:
    return f2(n-1)
     

fonction f3 :

def f3(n: int) -> int:
if n==0:
    return f3(n-1)
else:
    return 0

fonction f4 :

def f4(n: int) -> int:
if n==0:
    return n-1
else:
    return 0
        

fonction f5 :

def reduire(n:int) -> int:
    return n-1
def f5(n: int) -> int:
    if n==0:
        return 0
    else:
        return reduire(n)
        

Voici une fonction mystère nommée myst :

def myst(l: list) -> int:
    if l==[]:
        return 0
    else:          
        l.pop(0)          # suppression du premier terme de la liste l
        return 1+myst(l)
     

1. Pourquoi cette fonction myst est une fonction récursive ?

2. Testez cette fonction avec quelques listes.

3. Quel est le rôle de cette fonction myst ?

1. Copiez et lancez le script suivant :

   def appel() -> None:
       print("Allô ?")
       return appel()
   

2. Que remarquez-vous ? Comment expliquez-vous cela ?

On veut réaliser un château de cartes géants qui prolonge la château de l'image ci-dessous :

On note $n$ le nombre d'étages du château et $nb\_cartes(n)$ le nombre de cartes nécessaires pour réaliser un château à $n$ étages.

On admet que l'on peut connaître le nombre $nb\_cartes(n+1)$ de cartes nécessaires pour un château à $n+1$ étages si on connaît déjà le nombre $nb\_cartes(n)$ en utilisant la relation suivante (appelée relation de récurrence en mathématiques) : $$nb\_cartes(n+1)= nb\_cartes(n)+2+3 \times n$$

On veut à partir de ces informations construire une fonction récursive nommée nb_cartes qui renvoie finalement le nombre $nb\_cartes(n)$ si en argument lui est entré le nombre $n$ d'étages voulus au château.
Voici un script incomplet pour cette fonction :

def nb_cartes(n: int) -> int:
    if ...........: # condition d'arrêt
        return .............
    else:           # cas général
        return .............
        

1. En vous aidant de la relation de récurrence liant $nb\_cartes(n+1)$ et $nb\_cartes(n)$, complétez le retour du cas général.

2. Déterminez quel cas simple correspond à la condition d'arrêt puis complétez son renvoi.

3. Testez votre fonction obtenue.

   Vous pouvez utiliser l'image ci-dessus pour connaître quelques valeurs à obtenir.

4. Rajouter une précondition pour assurer le bon fonctionnement de l'algorithme.

La factorielle d'un entier naturel $n$ non nul, notée $n!$, est le produit de tous les nombres entiers compris entre 1 et $n$, c'est-à-dire : $n!=1 \times 2 \times ... \times (n-1) \times n$.

Il existe une relation "simple" entre $n!$ et $(n-1)!$.
En effet : $n!=1 \times 2 \times ... \times (n-1) \times n = \underbrace{1 \times 2 \times ... \times (n-1)}_{(n-1)!} \times n = (n-1)! \times n$,

1. Écrivez une fonction récursive fact qui prend comme argument l'entier non nul $n$ et qui renvoie $n!$ :

2. Quelle est la condition d'arrêt de votre fonction récursive ?

3. Pourquoi pouvez-vous être certain.e.s que la situation de terminaison sera atteinte après un nombre fini d'appels récursifs ?

4. Rajouter une précondition.

Le but est d'écrire une fonction récursive somme qui prend en argument une liste de nombres et qui renvoie la somme de ce nombres.

1. Quel cas simple peut correspondre à une condition d'arrêt pour cette fonction ?

2. Pour le cas général, proposez un appel récursif à la fonction somme où la liste est diminuée d'un élément.

   Vous pouvez vous aider :

   • soit d'une partie du script de l'exercice 4 (cf. lien direct),

   • soit en utilisant le slicing : liste[1:] correspond à la liste initiale où le premier élément a été ôté.

     Sachez que le slicing est hors programme donc non exigible en évaluation mais il permet ici d'écrire facilement le code voulu sans utiliser la méthode pop.

3. Testez votre fonction somme.

   Vous devez par exemple obtenir comme exécution de somme([1,2,3]) le nombre 6.

4. Quelle suite de nombres entiers strictement décroissante peut être exhibée ici afin de justifier la terminaison de l'algorithme écrit ?

On reprend la fonction récursive de l'exemple 1 (cf. lien direct). Cette fonction récursive nb_bact renvoie le nombre de bactéries au bout de $n$ jours, $n$ étant un entier naturel saisi comme argument.

def nb_bact(n: int) -> int:
    if n==0:
        return 10
    else:
        return 4*nb_bact(n-1)
    

Sur une feuille, faire apparaître sous forme d'un schéma comme ci-dessus les différentes étapes liées à l'empilement puis au dépilement de la pile d'exécution lorsque l'on veut exécuter le code suivant :

>>>nb_bact(4)
    

Considérons la suite dite de Fibonacci.

Le problème le plus célèbre du Liber abaci est le suivant : Combien de couples de lapins aurons-nous à la fin de l'année si nous commençons avec un couple qui engendre chaque mois un autre couple qui procréé à son tour au bout de deux mois ? Cet énoncé sous-entend les conditions suivantes :

1. La maturité sexuelle du lapin est atteinte après un mois qui est aussi la durée de gestation.

2. Chaque portée comporte toujours un mâle et une femelle.

3. Les lapins ne meurent pas !!

Si on note $couple(n)$ le nombre de lapins au bout de $n$ mois, on peut modéliser le problème "pratique" par une suite $(couple(n))$. Cette suite $(couple(n))$ est définie par la relation de récurrence suivante : \begin{equation} couple(n)=\begin{cases} 1 &, \text{si $n=0$}.\\ 1 &, \text{si $n=1$}.\\ couple(n-1) + couple(n-2) &, \text{si $n>1$}. \end{cases} \end{equation}

1. Écrivez une fonction récursive Fibo qui prend comme argument un entier naturel $n$ et qui renvoie le nombre $couple(n)$.

2. Testez votre fonction récursive en exécutant Fibo(10). Remarquez-vous quelque chose de particulier ?

3. Testez votre fonction récursive en exécutant Fibo(35). Remarquez-vous quelque chose de particulier ?

Code de déblocage de la correction :

4. Calculez le nombre d'appels effectués pour obtenir Fibo(4).

5. Faire de même avec Fibo(5). Calculer le coefficient multiplicateur pour passer du nombre d'appel pour Fibo(4) à celui pour Fibo(5).

6. En admettant que le coefficient multiplicateur obtenu à la question précédente reste en gros vrai quant au coût pour passaer de Fibo(n) à Fibo(n+1), déduire comment se comporte la compléxité en mémoire de cet algorithme.

Code de déblocage de la correction :

Écrire une procédure récursive qui demande un nombre positif à l’utilisateur et qui affichera ce nombre que s’il est positif. Sinon, demander à l’utilisateur de recommencer.

Dans le sud champardennais, un espace protégé Natura 2000 possède une faune d'insectes remarquables, en particulier un papillon appelé le "fadet des tourbières".
Comme cette espèce de papillon est désormais considérée comme menacée en France, l'espace protégé cherche à y maintenir, voire à y développer la population de ce cette espèce grâce à un dispositif mis en place à partir de 2020.
En 2020, la population de fadets des tourbières est estimée à 150 individus dans l'espace protégé.
On note $nb\_fadet(n)$ la population de papillon de cette espèce vivant dans l'espace protégé $n$ années après 2020.
Les écologues responsables du dispositifs espèrent que chaque année 80% de la poplulation précèdente reste et que 50 individus s'installent dans l'espace protégé.
On peut donc écrire cette relation ainsi : $nb\_fadet(n+1)=0.8 \times nb\_fadet(n)+50$.

1. En admettant cette relation, proposez une fonction recursive nb_fadet qui prend comme argument l'entier naturel $n$ et renvoie la population $nb\_fadet(n)$ estimée pour l'année $2020+n$.

2. Au vu du modèle, peut-on espérer une sauvegarde de l'espèce dans la zone protégée ?