SujetCorrigé

Devoir sur la récursivité

L'usage de la calculatrice n'est pas autorisé.

Durée : 55 min

Exercice 1

Soit la fonction myst suivante:

def myst(n,p):
    if p==0:
        return 0
    else:
        return n+myst(n,p-1)

Explique ce qu'elle permet de calculer.

Exercice 2

Écrire une fonction récursive qui permet de calculer la somme des \(n\) premiers nombres entiers.

Exercice 3

On souhaite écrire une fonction récursive compter(v, tab, i) qui compte le nombre d'occurences de v dans le tableau tab entre la case d'indice i et la dernière.

Voici quelques exemples:

>>> compter(3, [3, 2, 3, 5], 0) 
2 
>>> compter(3, [3, 2, 3, 5], 2) 
1 
>>> compter(3, [3, 2, 3, 5], 3) 
0

1. Quel devrait-être le résultat de:

   a. compter(4, [2, 4, 3], 2)

   b. compter(4, [2, 4, 3], 1)

   c. compter(4, [2, 4, 3], 0)

2. Donner la relation entre compter(s, tab, i) et compter(s, tab, i+1) et tab[i], si i est strictement inférieur à la longueur de tab.

3. Dans quel cas est-ce que la fonction renvoie directement une réponse et ne fait pas d'appel récursif ?

4. Écrire la fonction compter(s, tab, i) en Python. Vous pouvez utiliser len(tab).

Exercice 4

Proposez une fonction qui concatène ("colle") deux listes passées en paramètres.

Votre fonction doit être récursive.

Les seules méthodes sur les listes auxquelles vous avez droit sont :

• liste.ajouter(elt) qui ajoute un élément elt à la fin de la liste liste,
• liste.retirer() qui retourne le premier élément de la liste et supprime cet élément de la liste.

Exercice 5

À l'aide du module turtle, donne une fonction récursive qui permettrait de dessiner la figure suivante:

Exercice 1

La fonction myst(n,p) retourne le produit de n et de p.

Exercice 2

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

Exercice 3

1. a) 0 b) 1 c) 1

2. compter(s,tab,i)= s==tab[i]+compter(s,tab,i+1)

3. Si la liste à explorer n'a plus d'éléments, c'est à dire si i==len(tab).

4. def compter(s,tab,i):
     if i==len(tab):
       return 0
     else:
       return s==tab[i]+compter(s,tab,i+1)
   

Exercice 4

def concatene(L1,L2):
  if L2==[]:
    return L1
  else:
    return concatene(L1.ajouter(L2.retirer()),L2)

Exercice 5

def arbre(l,n):
  if n==0:
    forward(l)
    penup()
    backward(l)
    pendown()
  else:
    left(15)
    forward(l)
    arbre(l,n-1)
    penup()
    backward(l)
    pendown()
    right(30)
    forward(l)
    arbre(l,n-1)
    penup()
    backward(l)
    pendown()
    left(15)