Exercices#

Exercice 1#

On donne la fonction suivante:

image

  1. Expliquer pourquoi la fonction ordre(n) est récursive.

  2. Que renvoie l’appel ordre(4) ?

  3. Que se passe-t-il si on change la dernière instruction par return str(n)+ordre(n-1) ?

Exercice 2#

On donne la fonction suivante:

image

  1. Expliquer pourquoi la fonction compte(n) est récursive.

  2. Que renvoie l’appel compte(5) ?

  3. Que se passe-t-il si on change la dernière instruction par return 1+compte(n-2) ?

Exercice 3#

On donne le script suivant et la table de caractères ASCII:

image image1

On rappelle que la fonction Python chr(n) prend en argument un nombre entier n en écriture décimale et renvoie le caractère ASCII associé.

  1. Quelle est la valeur renvoyée par la commande chr(65) ?

  2. Quel est l’affichage à l’issu du script ?

  3. Écrire la fonction récursive affiche_recursif renvoyant le même résultat que le script ci-dessus.

Exercice 4#

Lorsqu’on effectue une remise de 10% sur un prix, cela revient à multiplier ce prix par la valeur \(1-10/100\).

On veut calculer des baisses successives de 10% sur une valeur, le nombre de remises étant défini à l’avance.

  1. Calculer trois remises successives de 10% sur un prix de 100 €.

  2. Montrer en détaillant le calcul qu’un algorithme récursif peut s’appliquer.

  3. Écrire un script itératif qui calcule \(n\) remises successives de 10% sur un prix. On utilisera les variables prix et n. La variable prix contiendra la valeur finale.

  4. Vérifier votre script avec un prix de 100 pour \(n=3\) remises.

  5. Écrire la fonction récursive remise_successive qui calcule \(n\) remise de 10% sur un prix défini à l’avance.

Exercice 5#

En mathématiques, pour trouver le plus grand commun diviseur de 2 nombres entiers, on applique l’algorithme d’Euclide, donné ci-dessous en python:

image

  1. S’agit-il d’une fonction récursive ? Pourquoi ?

    1. Que calcule l’opération \(a\%b\) dans la dernière ligne de la fonction ?

    2. Quelle est la valeur de \(12\%7\) ?

    3. Que se passe-t-il si \(a\) est strictement inférieur à \(b\) ?

  3. Quelle est la signification des instructions aux lignes 2 et 3 de la fonction ?

  4. Donner les différentes phases d’exécution de l’appel pgcd(28,42).

Exercice 6#

  1. Calculer :

    1. \(1 \times 2\)

    2. \(1 \times 2 \times 3\)

    3. \(1 \times 2 \times 3 \times 4\)

    4. \(1 \times 2 \times 3 \times 4 \times 5\)

  2. Les produits précédents sont des factorielles que l’on va noter factorielle(n) où n est un nombre entier.

    1. Quelle relation peut-on écrire entre factorielle(3) et factorielle(2) ?

    2. Quelle relation peut-on écrire entre factorielle(4) et factorielle(3) ?

    3. Pour tout nombre entier \(n\), écrire une relation entre factorielle(n) et factorielle(n-1).

  3. Écrire la fonction récursive factorielle(n) qui prend en paramètre un nombre entier \(n\) et renvoie la valeur de sa factorielle. On admet que factorielle(1) renvoie la valeur 1.

Exercice#

  1. Expliquer quel est le résultat renvoyé par le code suivant:

    image

  2. Écrire une fonction binaire qui prend en paramètres un entier relatif \(r\) et un entier naturel \(n\) strictement positif, et qui renvoie la représentation en machine de \(r\) sur \(n\) bits. La méthode utilisée est celle du complément à \(2\).

    Note

    Déterminer l’écriture binaire sur \(n\) bits d’un nombre négatif \(r\) revient à déterminer l’écriture binaire du nombre positif \(r+2^{n}\) (méthode du complément à 2)

    Exemple de l’écriture binaire du nombre \(-35\) sur 7 bits est \(-35+2^{7}=93=1011101_{2}\).

Exercice#

  1. Saisir le programme ci-dessous et le tester:

    image

  2. Donner une version récursive de ce code et vérifier qu’il donne bien le même résultat.

Exercice#

La fonction fibonacci(n), qui doit son nom au mathématicien Leonardo Fibonacci, est définie récursivement, pout tout entier \(n\), de la manière suivante:

\[\begin{split}\begin{aligned} \text{fibonnacci}(n)=\left\lbrace \begin{array}{ll} 0 & \text{si~} n=0,\\ 1 & \text{si~} n=1,\\ \text{fibonnacci}(n-2) + \text{fibonnacci}(n-1) & \text{si~} n>1.\\ \end{array} \right. \end{aligned}\end{split}\]

  1. Calculer fibonacci(5).

  2. Écrire en python cette fonction fibonacci.