Fonctions récursives

Suites définies par une relation de récurrence¶

Suites géométriques¶

On dit qu'une suite $(u_n)$ est géométrique lorsqu'il existe un nombre réel $a$ et un nombre réel $q$ tels que $u_0 = a$ et que pour tout $n \geq 1$ on ait $u_{n} = q\times u_{n - 1}$. On écrit souvent ces informations de la manière suivante :

\[ u_n = \begin{cases} a \quad \textrm{si } n = 0 \\ q\times u_{n - 1} \quad \textrm{sinon.} \end{cases} \]

Écrire le code d'une fonction récursive géométrique qui prend en argument un entier n, deux nombres flottants a et q, et qui renvoie $u_n$, quand $(u_n)$ est une suite géométrique de raison $q$ et de premier terme $a$.

###

def géométrique(n, a, q):bksl-nl """ int, float, float -> floatbksl-nl Renvoie upy-undn quand (upy-undn) est une suite géométrique de premier terme a et de raison q. """bksl-nl passbksl-nlbksl-nl

Suite arithmétiques¶

On dit qu'une suite $(u_n)$ est arithmétique lorsqu'il existe un nombre réel $a$ et un nombre réel $q$ tels que $u_0 = a$ et que pour tout $n \geq 1$ on ait $u_{n} = q + u_{n - 1}$. On écrit souvent ces informations de la manière suivante :

\[ u_n = \begin{cases} a \quad \textrm{si } n = 0 \\ q + u_{n - 1} \quad \textrm{sinon.} \end{cases} \]

Écrire le code d'une fonction récursive arithmétique qui prend en argument un entier n, deux nombres flottants a et q, et qui renvoie $u_n$, quand $(u_n)$ est une suite arithmétique de raison $q$ et de premier terme $a$.

###

def arithmétique(n, a, q):bksl-nl """ int, float, float -> float """bksl-nl passbksl-nlbksl-nl

Fonction factorielle¶

Pour tout entier positif ou nul on définit la fonction factorielle de $n$ de la manière suivante :

Si $n = 0$, alors la factorielle de $n$ vaut 1 ;
Sinon, la factorielle de $n$ vaut le produit des $n$ premiers entiers strictement positifs : $1 \times 2\times 3 \times \ldots \times n$.

On note $n!$ le nombre factorielle de $n$

Écrire une fonction python récursive factorielle qui prend en argument un entier positif n et qui renvoie le nombre $n!$.

###

def factorielle(n):bksl-nl """ int -> int """bksl-nl passbksl-nlbksl-nl

Suite de Fibonnacci¶

La suite doit son nom à Leonardo Fibonacci qui, dans un problème récréatif posé dans l'ouvrage Liber abaci publié en 1202, décrit la croissance d'une population de lapins :

« Quelqu’un a déposé un couple de lapins dans un certain lieu, clos de toutes parts, pour savoir combien de couples seraient issus de cette paire en une année, car il est dans leur nature de générer un autre couple en un seul mois, et qu’ils enfantent dans le second mois après leur naissance. »

On note $F_n$ le nombre de lapins présents au début du $n$-ième mois. Jusqu'à la fin du deuxième mois, les lapins n'ont pas commencé à se reproduire, il y a donc $F_1 = F_2 = 1$ couple. Lorsque $n \geq 3$, on admet que le nombre $F_n$ de couples lors du $n$-ième mois est donné par la formule suivante : $$ F_n = F_{n-2} + F_{n - 1} $$

Calculer les 10 premiers nombres de fibonacci.
Écrire une fonction récursive fibonacci qui prend en argument un entier positif n et qui calcule le nombre $F_n$.

###

def fibonacci(n):bksl-nl """ int -> int bksl-nl n >= 1bksl-nl Détermine le n-ième nombre de Fibonacci avec Fpy-und0 = 0, Fpy-und1 = 1. """bksl-nl passbksl-nlbksl-nl

Fonctions récursives¶

Encadre¶

L'objectif de cet exercice est d'écrire une version récursive de la fonction encadre qui étant donné un nombre entier k détermine la valeur du plus grand entier $n$ que l'on puisse écrire en base 2 avec k bits.

Pour quelles valeurs de $k$ est-il facile de calculer encadre(k) ?
On suppose dans cette question qu'un nombre entier $n$ s'écrit en base 2 avec $k$ bits.
1. Quel est le plus grand entier $n$ que l'on puisse écrire avec $k - 1$ bits ?
  
  Exprimer $n$ en fonction de $k$.
2. Quel est le plus grand entier $n$ que l'on puisse écrire avec $k$ bits ?
  
  Exprimer $n$ en fonction de $k$.
3. En déduire l'expression de encadre(k) en fonction de encadre(k-1).
En déduire le code d'une fonction récursive encadre qui réponde au problème de l'énoncé.

###

def testpy-undencadre():bksl-nl """ Tests pour la fonction encadre """bksl-nl maxs = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]bksl-nl for i in range(len(maxs)):bksl-nl expected = maxs[i]bksl-nl assert encadre(i + 1) == expected, message(i + 1, encadre(i + 1), expected)bksl-nl print("Tests de encadre passés avec succès")bksl-nl return Truebksl-nlbksl-nl# from tp import encadrebksl-nl# testpy-undencadre()bksl-nlbksl-nl 5/5

def encadre(k):bksl-nl """ int -> intbksl-nl Détermine le plus grand entier que l'on puisse écrire sur k bits """bksl-nl passbksl-nlbksl-nl

Nombres de bits¶

L'objectif de cet exercice est d'écrire une version récursive de la fonction nombre_bits qui étant donné un entier n détermine le nombre k de bits présents dans l'écriture en base 2 du nombre n.

Pour quelle(s) valeur(s) de $n$ est-il facile de calculer nombre_bits(n) ?
On suppose dans cette question qu'un nombre entier $n$ s'écrit en base 2 avec $k$ bits.
1. Avec combien de bits s'écrit en base 2 le nombre n//2 ?
  
  Exprimer la réponse en fonction de $k$.
2. En déduire l'expression de nombre_bits(n) en fonction de nombre_bits(n//2).
En déduire le code d'une fonction récursive nombre_bits qui réponde au problème de l'énoncé.

###

import mathbksl-nldef testpy-undnombrepy-undbits():bksl-nl """ Tests pour la fonction nombrepy-undbits """bksl-nl for i in range(1, 1024):bksl-nl expected = int(math.log2(i)) + 1bksl-nl assert nombrepy-undbits(i) == expected, message(i, estpy-undpair(bits), expected)bksl-nl print("Tests de nombrepy-undbits passés avec succès")bksl-nl return Truebksl-nlbksl-nl# from tp import nombrepy-undbitsbksl-nl# testpy-undnombrepy-undbits()bksl-nlbksl-nl 5/5

def nombrepy-undbits(n):bksl-nl """ int -> intbksl-nl Renvoie le nombre de bits nécessaires pour écrire n en base 2 """bksl-nl passbksl-nlbksl-nl

Appartient¶

L'objectif de cet exercice est d'écrire une version récursive de la fonction appartient qui étant donné un tableau (éventuellement vide) tab d'entiers et entier e, détermine si l'élément e est présent dans le tableau tab. On commence pour cela par écrire une fonction appartient_aux qui étant donné un tableau (éventuellement vide) tab d'entiers, un entier e et un entier i détermine si l'élément e est présent parmi les i premiers éléments du tableau tab. Si $n$ est la taille du tableau tab, on supposera que $0 \leq i \leq n$.

Soient tab un tableau et e un élément.

Que doit renvoyer l'instruction appartient(tab, e, 0) ? 2. On suppose dans cette questions que $1 \leq i \leq n$. 1. Quel est l'indice du $i$-ème élément du tableau tab ?
```
Exprimer votre réponse en fonction de $i$.
```
1. Avec quels arguments faut-il appeler la fonction appartient_aux pour déterminer si l'élément e est présent parmi les $i - 1$ premiers éléments du tableau ?
2. Décommenter et compléter le code ci-dessous.

def appartient_aux(tab, e, i):
    """ [int], int, int -> bool 
    0 <= i <= len(tab)
    Détermine si l'élément e est présent parmi les i premiers éléments de tab. """
    # if i == 0:
        # return ...............................
    # else:
        # On teste si le i-ème élément du tableau est l'élément recherché.
        # if tab[............] == .............:
        #     return ...........................
        # Sinon on recherche l'élément e parmi les i-1 premiers éléments. 
        # else:
        #     return ...........................

def appartient(tab, e):
    """ [int], int -> bool 
    Détermine si l'élément e est présent dans le tableau tab. """
    # return .....................................

Nombre d'occurrences¶

En vous inspirant de l'algorithme de l'exercice précédent, écrire une fonction nombre_occurrences_aux qui étant donné un tableau (éventuellement vide) tab d'entiers, un entier e, et un entier i détermine le nombre de fois où l'élément e est apparait parmi les i premiers éléments du tableau tab. Si $n$ est la taille du tableau tab, on supposera que $0 \leq i \leq n$.

def nombre_occurrences_aux(tab, e, i):
    """ [int], int, int -> int
    0 <= i <= len(tab)
    Renvoie le nombre d'occurences de e parmi les i premiers éléments de tab """
    pass