C1 Recursivité - Activités

Activités

Activité 1 : A la découverte de la récursivité

L'escalier
1. Ecrire un programme Python permettant de tracer un escalier tel que ci-dessous en répétant le motif de base (le tracé d'une marche):
2. Pour réaliser le dessin ci-dessus vous avez probablement utilisé une boucle, votre programme est dit itératif. Remarquons à présent que l'escalier à construire était composé de 8 marches. On pourrait écrire qu'un escalier de 8 marches, c'est une marche suivi d'un escalier de 7 marches. Nous venons de donner une définition récursive c'est à dire qu'on a définit un escalier par rapport à lui même. Les fonctions de Python peuvent de la même façon faire appelle à elle-même et donc être récursive. Par exemple :
```
def dessine_escalier(nb_marches):
    dessine_une_marche()
    dessine_escalier(nb_marche-1)
```
  Intégrer cette fonction dans le programme précédant, écrire la fonction dessine_une_marche puis tester. Que se passe-t-il ?
3. Intégrer une condition d'arrêt : si nb_marches est négatif ou nul, ne rien faire. Tester de nouveau.
Le dessin de la frise ci-dessous est constitué de la répétition d'un motif de base (en rouge).
1. Ecrire une fonction motif() qui dessine le motif de base (les dimensions sont indiquées sur l'illustration ci-dessous):
2. A l'aide d'un programme itératif, construire la frise.
3. Donner une définition récursive de la frise
4. Ecrire une fonction récursive permettant de construire la frise.
La spirale
1. Ecrire un programme Python itératif permettant de tracer la spirale de carré suivante sachant que :
  - Le côté du grand carré initial mesure 200 pixels
  - Le coin inférieur gauche des carrés est l'origine du repère
  - A chaque étape les carrés tournent de 20°
  - A chaque étape la côté du carré diminue de 10% de sa longueur.
  - On interrompt la construction lorsque la taille est inférieure ou égale à 10 pixels
2. On déompose la spirale en un premier carré (en trait épais ci dessous), suivi d'une spirale de carrés (en gris et traits fin ci-dessous) : En déduire une définition récursive de la spirale.
3. Proposer une fonction récursive permettant de construire la spirale.

Activité 2 : D'autres exemples de récursivité

Somme des n premiers entiers
1. Ecrire une fonction python somme(n) itérative qui calcule la somme des n premiers entiers. Par exemple somme(5) renvoie 15 puisque 1+2+3+4+5=15.
2. Compléter l'égalité mathématique suivante entre somme(n) et somme(n-1) :
  somme(n) = somme(n-1) + ...
3. En déduire une version récursive de la fonction somme(n)
Écrire à l'envers
1. Compléter puis tester le code de la fonction Python ci-dessous qui prend en argument une chaine de caractère et la renvoie écrite à l'envers
```
def envers(chaine):
resultat = ""
for caractere in .....:
    resultat = ...... + resultat
return .....
```
2. On décompose une chaine en chaine = debut + dernier caractère, compléter la définition récursive suivante : envers(chaine) = .......... + envers(.......)
3. En déduire une version récursive de la fonction envers
  
  Aide
  
  On pourra écrire au préalable une fonction debut(chaine) qui renvoie la chaine privée de son dernier caractère. On rapelle que le dernier caractère de chaine s'obtient avec chaine[-1].

Activité 3 : Soulever le capot de la récursivité

Se rendre sur le site Python tutor, un outil en ligne permettant de visualiser le fonctionnement d'un programme Python. Laisser les options par défaut à l'exception de inline primitives don't nest objects [default] ) à remplacer par render all objects on the heap (Python/Java) comme ci-dessous :

Entrer sur Python tutor le code de fonction somme(n) itérative, qu'on teste avec n=5 :

def somme(n):
    s = 0
    for i in range(n):
        s+=i
    return s

test = somme(5)

Suivre l'exécution pas à pas du calcul.

Faire de même mais avec la fonction somme_recursive(n) :

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

test =  somme_recursive(5)

La figure suivante représente une étape de l'exécution. Comment expliquer que les entiers sont "stockés" à droite mais qu'aucun calcul n'a encore été effectué ?
La colonne de droite où sont stockés les entiers s'appelle une pile, (heap en anglais). La taille maximale de cette pile est la profondeur maximale de récursion (recursion depth). Quitter Python Tutor et tester la fonction somme_recursive avec une valeur élevée de n (par exemple n=3000). Que se passe-t-il ? Expliquer.
La version itérative est-elle concernée par ce problème ?