Devoir sur la récursivité
L'usage de la calculatrice n'est pas autorisé.
Le barème est donné à titre indicatif
Durée : 55 min
Exercice 1
Écrire une fonction récursive triangle
qui prend en paramètre un entier \(n\) et affiche un triangle :
>>> triangle(6)
******
*****
****
***
**
*
Corrigé
def triangle(n):
if n>0:
res=""
for i in range(n):
res=res+"*"
print(res)
triangle(n-1)
def triangle(n):
if n>0:
print(n*"*")
triangle(n-1)
Exercice 2
Voici une fonction f
d'un ancien examen de fin d’études secondaires :
def f(s):
if len(s) <= 1:
return s
if len(s) == 2:
return s[1] + s[0]
return s[-1] + f(s[1:len(s) - 1]) + s[0]
-
Exécutez cette fonction en prenant comme argument 'recursive'. (Écrire toutes les étapes !)
-
Que retourne cette fonction en général ?
-
On peut simplifier cette fonction sans que le résultat soit différent ! Quelles lignes sont superflues ?
-
Écrire une version itérative de cette fonction.
Corrigé
-
Première exécution
f("recursive") "e"+f("ecursiv")+"r" "e"+"v"+"cursi"+"e"+"r" "e"+"v"+"i"+"urs"+"c"+"e"+"r" "e"+"v"+"i"+"s"+"r"+"u"+"c"+"e"+"r" et on remonte en retournant : "evisrucer"
-
Cette fonction retourne la chaïne de caractères lues à l'envers.
-
Les lignes superflues sont:
if len(s) == 2: return s[1] + s[0]
-
La version itérative:
def g(s): res="" for elt in s: res=elt+res return res
Exercice 3
Proposer un algorithme récursif qui calcule la puissance d’un nombre.
>>> puissance(3, 2)
9
Corrigé
def puissance(a,n):
if n==0:
return 1
else:
return a*puissance(a,n-1)
Exercice 4
Soit la fonction mystere
suivante:
def recurse(n):
if n>0:
for i in range(4):
forward(50)
right(90)
left(45)
forward(50)
recurse(n-1)
Que permet de dessiner l'instruction recurse(20)
?
Corrigé
Exercice 5
Écrire un programme qui permet de dessiner :
Corrigé
Solution un peu longue et pas très élégante (des traits en trop)
def carre(n,L):
if n>0:
for i in range(4):
forward(L)
left(90)
penup()
forward(L)
pendown()
carre(n-1,L/2)
penup()
backward(L)
left(90)
forward(L)
right(90)
pendown()
carre(n-1,L/2)
penup()
left(90)
backward(L)
right(90)
pendown()
````
Un peu plus courte :
```python
def carre(n,L):
if n>0:
forward(L)
carre(n-1,L/2)
left(90)
forward(L)
left(90)
forward(L)
left(180)
carre(n-1,L/2)
left(90)
backward(L)
right(90)