Aller au contenu

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)
ou bien, plus rapide et élégant:

    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]
  1. Exécutez cette fonction en prenant comme argument 'recursive'. (Écrire toutes les étapes !)

  2. Que retourne cette fonction en général ?

  3. On peut simplifier cette fonction sans que le résultat soit différent ! Quelles lignes sont superflues ?

  4. Écrire une version itérative de cette fonction.

Corrigé
  1. 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"
    
  2. Cette fonction retourne la chaïne de caractères lues à l'envers.

  3. Les lignes superflues sont:

    if len(s) == 2:
        return s[1] + s[0]
    
  4. 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)