C1 Recursivité - Exercices

Exercices

Exercice 1 : Factorielle

En mathématiques, on appel factorielle d'un entier $n$ et on $n!$ le produit de cet entier par tous ceux qui le précèdent à l'exception de zéro. On convient d'autre part que $0! = 1$ . Par exemple,
$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ .

Programmer une version itérative d'une fonction factorielle(n) qui renvoie factorielle de l'entier positif n passé en argument.
Recopier et compléter :
$n! = n \times \underset{. . .}{\underset{⏟}{(n - 1) \times \dots \times 1}}$
$n! = n \times \dots$
En déduire une version récursive de la fonction factorielle(n).

Exercice 2 : Analyser un programme récursif

On considère la fonction mystere ci-dessous :

def mystere(liste):
    if len(liste)==1:
        return liste[0]
    else:
        if liste[0]<liste[1]:
            liste.pop(1)
        else:
            liste.pop(0)
        return mystere(liste)

Analyser ce programme, en déduire le rôle de cette fonction.

Aide

Faire fonctionner "à la main" ce programme sur une liste de petite taille, revoir le rôle de pop si nécessaire.
Donner une version itérative de cette fonction

Exercice 3 : Comprendre un programme récursif

On donne le code incomplet d'une fonction récursive permettant de calculer le produit de deux entiers positifs a et b en effectuant uniquement des additions :

def produit(a,b):
    if b==...:
        return ...
    else:
        return ...+produit(...,...)

Compléter les égalités suivantes :
- $a \times 0 = \dots$
- $a \times b = a + a \times (\dots \dots)$
Compléter le code de la fonction ci-dessus et la tester
Que se passe-t-il si on choisit une valeur assez grande pour b, par exemple 5000 ? Pourquoi ? En est-il de même pour de grandes valeurs de a ? Pourquoi ?
Améliorer le code de cette fonction de façon à ce que le dépassement de pile de récursion n'arrive que lorsque a et b sont tous deux supérieurs à la taille maximale.

Exercice 4 : Additions et soustractions

On suppose qu'on ne dispose que de deux opérations : ajouter 1 ou retrancher 1.

Écrire à l'aide de ces deux opérations, une version itérative de l'addition de deux entiers.
Même question avec une version récursive.

Exercice 5 : Comparaison de deux chaines de caractères

Ecrire de façon itérative, une fonction compare(chaine1,chaine2) qui renvoie le nombre de fois où chaine1 et chaine2 ont le même caractère au même emplacement. A titre d'exemples :
- compare("recursif","iteratif") renvoie 2,
- compare("Python","Javascript") renvoie 0.
Écrire cette même fonction de façon récursive.

Aide

Vous aurez peut être besoin d'une fonction reste(chaine) qui renvoie la chaine passée en paramètre privée de son premier élément. Par exemple reste("python") renvoie ython. Ecrire vous même cette fonction, ou chercher comment utiliser les slices de Python.

Exercice 6 : Comprendre la récursivité

Cet exercice est extrait d'un sujet de bac de la session 2022

Voici une fonction codée en Python :

def f(n):
    if n==0:
        print("Partez !")
    else:
        print(n)
        f(n-1)

Qu'affiche la commande f(5) ?
Pourquoi dit-on de cette fonction qu'elle est récursive ?

On rappelle qu'en Python, l'opérateur + a le comportement suivant sur les chaînes de caractères :
```
>>> S = 'a' + 'bc'
>>> S
'abc'
```
Et le comportement suivant sur les listes :
```
>>> L= ['a'] + ['b','c']
>>> L
['a','b','c']
```
On a besoin pour les questions suivantes de pouvoir ajouter une chaîne de caractères s en préfixe à chaque chaîne de caractères de la liste liste. On appellera cette fonction ajouter. Par exemple, ajouter("a",["b","c"]) doit retourner `["ab","ac"].
1. Recopier le code suivant en complétant la ligne 4:
  1 2 3 4 5
  def ajouter(s,liste): res = [] for m in liste: res............. return res
2. Que renvoie la commande ajouter("b",["a","b","c"]) ?
3. Que renvoie la commande ajouter("a",[""]) ?
On s'intéresse ici à la fonction suivante écrite en Python où s est une chaîne de caractères et n un entier naturel.
```
def produit(s, n):
    if n == 0:
        return [""]
    else:
        res = []
        for i in range(len(s)):
            res = res + ajouter(s[i], produit(s, n-1))
    return res
```
1. Que renvoie la commande produit("ab",0) ? Le résultat est-il une liste vide ?
2. Que renvoie la commande produit("ab",1) ?
3. Que renvoie la commande produit("ab",2) ?

Exercice 7 : Mélange d'une liste

Cet exercice est extrait d'un sujet de bac de la session 2021

On s'intéresse dans cet exercice à un algorithme de mélange des éléments d'une liste.

Pour la suite, il sera utile de disposer d'une fonction echange qui permet d'échanger dans une liste lst les éléments d'indice i1 et i2. Expliquer pourquoi le code Python ci-dessous ne réalise pas cet échange et en proposer une modification.
```
    def echange(lst, i1, i2):
        lst[i2] = lst[i1]
        lst[i1] = lst[i2]
```
La documentation du module random de Python fournit les informations ci-dessous concernant la fonction randint(a,b) :

Renvoie un entier aléatoire N tel que a <= N <= b. Alias pour randrange(a,b+1).

Parmi les valeurs ci-dessous, quelles sont celles qui peuvent être renvoyées par l'appel randint(0, 10) ?
0 1 3.5 9 10 11
Le mélange de Fischer Yates est un algorithme permettant de permuter aléatoirement les éléments d'une liste. On donne ci-dessous une mise en œuvre récursive de cet algorithme en Python.
```
from random import randint
def melange(lst, ind):
    print(lst)
    if ind > 0:
        j = randint(0, ind)
        echange(lst, ind, j)
        melange(lst, ind-1)
```
1. Expliquer pourquoi la fonction melange se termine toujours.
2. Lors de l’appel de la fonction melange, la valeur du paramètre ind doit être égal au plus grand indice possible de la liste lst. Pour une liste de longueur n, quel est le nombre d'appels récursifs de la fonction melange effectués, sans compter l’appel initial ?
3. On considère le script ci-dessous :
```
    lst=[v for v in range(5)]
    melange(lst,4)
```
  On suppose que les valeurs successivement renvoyées par la fonction randint sont 2, 1, 2 et 0. Les deux premiers affichages produits par l'instruction print(lst) de la fonction melange sont :
  [0,1,2,3,4]
  [0,1,4,3,2]
  Donner les affichages suivants produits par la fonction melange
4. Proposer une version itérative du mélange de Fischer Yates.

Exercice 8 : Recherche dichotomique dans un tableau trié

Rappeler l'algorithme de recherche dichotomique dans un tableau trié vu en classe de première et donner son fonctionnement sur un exemple simple.

Aide

Voir cette page du cours de première.
Coder cet algorithme de façon itérative
Coder cet algorithme de façon récursive