Chapitre 4 - Entraînement : Récursivité

Récursivité

Exercice 1 - Fonctions récursives de base

Écrire les fonctions récursives suivantes :

a. somme(n) : renvoie la somme des entiers de 1 à n.

b. compter_chiffres(n) : renvoie le nombre de chiffres d'un entier positif n.

c. renverser(chaine) : renvoie la chaîne de caractères inversée.

d. pgcd(a, b) : calcule le PGCD de a et b par l'algorithme d'Euclide.

def somme(n):
  pass

def compter_chiffres(n):
  pass

def renverser(chaine):
  pass

def pgcd(a, b):
  pass

Solution

def somme(n):
    if n == 0:
        return 0
    return n + somme(n - 1)

def compter_chiffres(n):
    if n < 10:
        return 1
    return 1 + compter_chiffres(n // 10)

def renverser(chaine):
    if len(chaine) <= 1:
        return chaine
    return chaine[-1] + renverser(chaine[:-1])

def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a % b)

Exercice 2 - Analyse de fonctions récursives

Pour chaque fonction, déterminer :

le cas de base ;
le cas récursif ;
le variant (preuve de terminaison) ;
le résultat de l'appel indiqué.

def mystere(n):
    if n == 0:
        return 0
    return n % 2 + mystere(n // 2)

Appel : mystere(13)

def f(chaine, c):
    if chaine == "":
        return 0
    if chaine[0] == c:
        return 1 + f(chaine[1:], c)
    return f(chaine[1:], c)

Appel : f("abracadabra", "a")

Solution

Cas de base : n == 0 → renvoie 0
Cas récursif : renvoie n % 2 + mystere(n // 2)
Variant : n (divisé par 2 à chaque appel, converge vers 0)
mystere(13) : 13 en binaire = 1101, donc la fonction compte le nombre de bits à 1. Résultat : 3.

Cas de base : chaine == "" → renvoie 0
Cas récursif : avance dans la chaîne (chaine[1:])
Variant : len(chaine) (décroît de 1 à chaque appel)
f("abracadabra", "a") : compte les occurrences de "a" → 5.

Exercice 3 - Dessins récursifs (fractales)

Écrire un programme Python utilisant le module turtle pour dessiner un flocon de Koch de manière récursive.

Le principe : à chaque niveau de récursion, chaque segment est remplacé par quatre segments formant une pointe triangulaire.

Solution

import turtle

def koch(t, longueur, niveau):
    if niveau == 0:
        t.forward(longueur)
    else:
        koch(t, longueur / 3, niveau - 1)
        t.left(60)
        koch(t, longueur / 3, niveau - 1)
        t.right(120)
        koch(t, longueur / 3, niveau - 1)
        t.left(60)
        koch(t, longueur / 3, niveau - 1)

def flocon(t, longueur, niveau):
    for _ in range(3):
        koch(t, longueur, niveau)
        t.right(120)

t = turtle.Turtle()
t.speed(0)
t.penup()
t.goto(-150, 90)
t.pendown()
flocon(t, 300, 4)
turtle.done()

Calculabilité et décidabilité

Exercice 4 - Programme comme donnée

a. Citer trois exemples de logiciels qui prennent un programme en entrée.

b. Expliquer pourquoi la calculabilité ne dépend pas du langage de programmation.

c. Qu'est-ce qu'un problème indécidable ? Donner un exemple.

Solution

a. Un compilateur (traduit du code source en code machine), un interpréteur (exécute le code ligne par ligne), un antivirus (analyse le comportement du programme).

b. Tous les langages de programmation « complets » (au sens de Turing) sont équivalents en puissance de calcul : ce qui peut être calculé dans un langage peut l'être dans tout autre. C'est la thèse de Church-Turing.

c. Un problème indécidable est un problème pour lequel il n'existe aucun algorithme capable de répondre correctement (oui ou non) dans tous les cas. Le problème de l'arrêt en est l'exemple principal : on ne peut pas écrire un programme qui détermine si tout programme termine.

Exercice 5 - Le problème de l'arrêt

Les programmes suivants s'arrêtent-ils ?

def pa(n):
    if n <= 0:
        return 0
    return pa(n - 2)

Appel : pa(7)

def pb(n):
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1

Appel : pb(6)

c. Expliquer pourquoi un programme ne pourrait pas répondre automatiquement à ces questions dans tous les cas.

Solution

a. pa(7) : 7 → 5 → 3 → 1 → -1 → -3 → ... La condition n <= 0 finit par être atteinte (pour n = -1). Oui, il s'arrête.

b. pb(6) : 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → sortie de boucle. Oui, il s'arrête. (C'est la suite de Syracuse, mais on ne sait pas si elle s'arrête pour tout n.)

c. C'est le problème de l'arrêt : Turing a prouvé qu'aucun programme ne peut déterminer si tout programme termine. L'analyse au cas par cas est possible, mais un algorithme général n'existe pas.

Activités

Activité 1 - Tours de Hanoï visuelles

Adapter le programme des tours de Hanoï pour afficher l'état des trois tiges après chaque déplacement, en utilisant des listes Python pour représenter les tiges.

Solution

def afficher_tiges(tiges):
    for nom in ['A', 'B', 'C']:
        print(f"  {nom} : {tiges[nom]}")
    print()

def hanoi(n, source, dest, inter, tiges):
    if n == 1:
        disque = tiges[source].pop()
        tiges[dest].append(disque)
        print(f"Déplacer disque {disque} de {source} vers {dest}")
        afficher_tiges(tiges)
        return
    hanoi(n - 1, source, inter, dest, tiges)
    disque = tiges[source].pop()
    tiges[dest].append(disque)
    print(f"Déplacer disque {disque} de {source} vers {dest}")
    afficher_tiges(tiges)
    hanoi(n - 1, inter, dest, source, tiges)

n = 3
tiges = {'A': list(range(n, 0, -1)), 'B': [], 'C': []}
print("État initial :")
afficher_tiges(tiges)
hanoi(n, 'A', 'C', 'B', tiges)

Projet

Projet - Interpréteur de mini-langage

Créer un interpréteur pour un mini-langage de programmation supportant :

les variables (x = 5) ;
les opérations arithmétiques (x + 3, x * y) ;
l'affichage (afficher x) ;
les conditions (si x > 0 alors afficher x) ;
les boucles (tant que x > 0 faire x = x - 1).

Solution

class Interpreteur:
    def __init__(self):
        self.variables = {}

    def evaluer_expression(self, expr):
        expr = expr.strip()
        for op in ['+', '-', '*', '/']:
            if op in expr:
                parties = expr.split(op, 1)
                gauche = self.evaluer_expression(parties[0])
                droite = self.evaluer_expression(parties[1])
                if op == '+': return gauche + droite
                if op == '-': return gauche - droite
                if op == '*': return gauche * droite
                if op == '/': return gauche / droite
        try:
            return float(expr)
        except ValueError:
            if expr in self.variables:
                return self.variables[expr]
            raise ValueError(f"Variable inconnue : {expr}")

    def evaluer_condition(self, cond):
        for op in ['>=', '<=', '!=', '>', '<', '==']:
            if op in cond:
                parties = cond.split(op)
                g = self.evaluer_expression(parties[0])
                d = self.evaluer_expression(parties[1])
                if op == '>': return g > d
                if op == '<': return g < d
                if op == '>=': return g >= d
                if op == '<=': return g <= d
                if op == '==': return g == d
                if op == '!=': return g != d
        return False

    def executer(self, ligne):
        ligne = ligne.strip()
        if ligne.startswith("afficher "):
            val = self.evaluer_expression(ligne[9:])
            print(val)
        elif ligne.startswith("si "):
            parties = ligne[3:].split(" alors ")
            if self.evaluer_condition(parties[0]):
                self.executer(parties[1])
        elif "=" in ligne and not any(op in ligne.split("=")[0] for op in ['>', '<', '!']):
            parties = ligne.split("=", 1)
            nom = parties[0].strip()
            valeur = self.evaluer_expression(parties[1])
            self.variables[nom] = valeur
        else:
            print(f"Instruction non reconnue : {ligne}")

    def executer_programme(self, code):
        for ligne in code.strip().split("\n"):
            if ligne.strip():
                self.executer(ligne)

interp = Interpreteur()
interp.executer_programme("""
x = 10
y = 3
z = x + y
afficher z
si x > 5 alors afficher x
si y > 5 alors afficher y
""")