La récursion

Définition : Une fonction est dite récursive, lorsqu'elle s'appelle elle même.

Exercice Centrale 2017 PC

La question la plus intéressante était la 3, mais la 1 et la 2 sont des questions mathématiques (combinatoire) qu'il est important de savoir faire sans trop perdre de temps.

Question 1

Question 2

Question 3

On a fait ici de la ✨programmation dynamique✨ :

dico={}
def S(n,k):
    assert n>=0 and k>=0
    if k==0 and n==0:
        return 1
    if k==0 or n==0:
        return 0
    if (n,k) in dico:
        return dico[(n,k)]
    else:
        dico[(n,k)] = S(n-1,k-1) + k*S(n-1,k)
        return dico[(n,k)]

Question 4

Résultat utile à savoir retrouver rapidement : $\binom{n}{k} \leq \frac{n^k}{k!}$

Cette question est hors-sujet, car notre programme est en ${\cal O}(n\times k)$ grâce à la programmation dynamique.

Nouvel éxo à faire si t'as le temps pour la prochaine fois (maybe jeudi)

Le plus important ce sont les questions 1 et 2 (tu peux faire les autres si tu veux/as le temps).

Essaie de tester les fonctions après les avoir codées.

Pour la question 1 on ne demande pas de créer une fonction, on demande uniquement d'écrire une suite d'instructions.

Exercice – Permutations des éléments d’une liste (récursion)

On rappelle qu’une permutation d’un ensemble L est une bijection de L sur lui-même, c’est-à-dire un réarrangement possible des éléments de L.

1. Génération des permutations d’une liste donnée

On suppose que P est une liste contenant toutes les permutations possibles de la liste [b, c, d], par exemple :

P = [
[b, c, d],
[c, b, d],
[c, d, b],
[b, d, c],
[d, b, c],
[d, c, b]
]

Écrire les instructions Python permettant d’obtenir la liste Q des permutations de la liste [a, b, c, d] à partir de P, sans modifier P.

On rappelle :

• Pour copier une liste sans la modifier :
  q = p.copy() ou q = p[:]
• Pour insérer un élément à une position donnée :
  q.insert(i, x)

2. Fonction récursive permutations(L)

Écrire une fonction récursive permutations(L) qui prend en argument une liste L et renvoie la liste de toutes les permutations de L.

Exemple d’utilisation :

L = ['a', 'b', 'c']
for p in permutations(L):
    print(p)

Résultat attendu (ordre non imposé) :

['a', 'b', 'c']
['b', 'a', 'c']
['b', 'c', 'a']
['a', 'c', 'b']
['c', 'a', 'b']
['c', 'b', 'a']

3. Justification de terminaison

Expliquer pourquoi votre fonction récursive termine toujours. (Vous pouvez raisonner sur la taille du problème à chaque appel récursif.)

4. Étude du nombre d’insertions

On note Cₙ le nombre total d’opérations q.insert(0, x) effectuées par votre programme pour générer toutes les permutations d’une liste de taille n.

1. Donner une relation de récurrence vérifiée par Cₙ.
2. Calculer la valeur explicite de Cₙ (en fonction de n).