Aller au contenu principal

TD1 - Prise en main de la récursivité

Objectifs
  1. Comprendre le concept de récursivité ;
  2. Identifier les cas d'arrêts et cas généraux ;
  3. Traduire un programme en récursif ;
  4. Écrire un programme récursif.
Les fonctions python
  1. Se créer un dossier Terminale NSI sur votre ordinateur ou clé USB
  2. Dans ce dossier, créer un dossier Récursivité

Sur EduPython ou autre instance python, faire :

  1. Créer un nouveau fichier en cliquant sur l'icône 📄, ou en appuyant sur CTRL+N
  2. Enregistrer le fichier sous le nom TP1_Prise_en_main en cliquant sur l'icône 💾, ou en appuyant sur CTRL+S
TD/TP

Les questions sont à répondre sur une feuille/document word.
Vous êtes autorisés à programmer les fonctions sur python.

Exercice 1​

On donne la fonction itérative suivante :

def fonction1(n):
    res = 1
    while n > 0 :
        res = res * n
        n = n - 1
    return res
  1. Expliquer ce que fait la fonction.
  2. Quel est le cas d’arrêt de la fonction ?
  3. Quel est le cas général de la fonction ?
  4. Écrire cette fonction en récursif en suivant les cas trouvés plus haut.
  5. La fonction s’arrête-elle toujours ? Expliquer.

Exercice 2​

L’algorithme d’Euclide permet de calculer le pgcd de deux nombres entiers, c’est-à-dire le plus grand entier positif divisant ces deux nombres, par des divisions successives.

  1. Écrire l’algorithme itératif du pgcd, avec 2 entiers en paramètres (on utilisera le modulo).
  2. Déterminer le cas d’arrêt de la fonction.
  3. Déterminer le cas général de la fonction.
  4. Écrire la méthode du pgcd en récursif, en suivant les cas énoncés plus haut.

Exercice 3​

La suite de Fibonacci est une suite mathématique définie comme suit :

  • À l’initialisation, F0 = 0;
  • À la première étape, F1 = 1;
  • À l’étape n, Fn = Fn−1 + Fn−2 pour n > 1.
  1. Déterminer les cas d’arrêt de la suite de Fibonacci.
  2. Déterminer le cas général de la suite de Fibonacci.
  3. Écrire l’algorithme récursif en suivant les cas énoncés plus haut.
  4. Expliquer pourquoi votre algorithme s’arrête.

Exercice 4​

Soit la fonction suivante :

def fonction2(chaine):
    res = 0
    while chaine != "" :
        res = res + 1
        chaine = chaine[1:]
    return res
  1. Que fait la fonction suivante ?
  2. Quel est son cas d’arrêt ?
  3. Quel est son cas général ?
  4. Écrire cette fonction en récursif.