Devoir sur la récursivité 2025-2026

L'usage de la calculatrice n'est pas autorisé et le barème est donné à titre indicatif

Durée : 55 min

Exercice 1 (2 points)

Définir une fonction récursive longueur(s) qui détermine la longueur d'une chaîne de caractères s.

def longueur(s):
    # cas particulier
    if s == ... :
        return ...
    # appel récursif
    else :
        return ...

Corrigé

def longueur(s):
    # cas particulier : chaîne vide
    if s == "":
        return 0
    # appel récursif : on retire le premier caractère et on ajoute 1
    else:
        return 1 + longueur(s[1:])

Exercice 2 (3 points)

On définit la fonction python ci-dessous dans laquelle L est une liste.

Rappel: si L = [7,8,9,10] alors L[0:3] vaut [7,8,9]

def r(deb, fin, L):
    if deb >= fin:
        print("fini")
    else:
        print(L[deb:fin])
        return  r(deb+1, fin, L)

Décrire sur papier les étapes lors de l'appel ci-dessous.

L = [2, 3, 4, 7, 11, 15, 17]
r(1,4, L)

Corrigé

[3, 4, 7]
[4, 7]
[7]
fini

Exercice 3 (2 points)

Faire le dessin de la figure obtenue lors de l'exécution de la fonction suivante:

def figure(n):
    if n>0:
        for i in range(3):
            forward(n*10)
            left(120)
    figure(n-1)

Corrigé

Exercice 4 (3 points)

Écrire une fonction nommée somme_listes_imbriquees, récursive, qui additionne tous les entiers des listes.

Exemple de listes imbriquées :

L1 = [1, [2, [3, 4], 5], 6, [7, 8]] L2 = [1, [2, [3, [4, [5]]]]]

Corrigé

def somme_listes_imbriquees(L):
    if L==[]:
        return 0
    else:
        if type(L[0])==List:
            return somme_listes_imbriquees(L[0])+somme_listes_imbriquees(L[1:])
        else:
            return L[0]+ somme_listes_imbriquees(L[1:])

Exercice 5 (3 points)

Écrire un programme récursif qui permet de représenter la figure suivante:

Corrigé

from turtle import *

def plus(t, n):
    if n>0:
        for i in range(4):
            forward(t*2/3)
            plus(t/2,n-1)
            backward(t*2/3)
            left(90)

speed('fastest')

plus(100, 3)