Récursivité

L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer la somme des $n$ nombres (entiers) d’un tableau.

1. Écrire le code de fonction somme1 dont la spécification est :

1
2
3
4
5
6
7

def somme1(tab: List[float]) -> float:
    """
    Calcul de la somme des nombres éléments
    de tab.

    Algorithme : Récursivité enveloppée
    """

Penser à écrire un jeu de tests.

Rappel : récursivité terminale

La définition de la fonction factorielle est $$ n! = \begin{cases} 1 & \text{if } n = 0 \cr n \times (n-1)! & \text{sinon} \end{cases} $$

1. Définir la fonction fact_env qui calcule la factorielle d’un entier naturel $n$, sans oublier le jeu de tests.
   La spécification de la fonction est :

   1 2 3 4 5 6

   def fact_env(n: int) -> int: """ Retourne la factorielle de n. Algorithme : récursivité enveloppée """

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def fact_env(n: int) -> int:
    """
    Retourne la factorielle de n.

    Algorithme : récursivité enveloppée
    """
    if n == 0:
        return 1

    return n * fact_env(n - 1)


if __name__ == "__main__":
    assert fact_env(0) == 1
    assert fact_env(1) == 1
    assert fact_env(5) == 120
    assert fact_env(8) == 40320

Introduction

Dans le code suivant (qu’il faudra étudier et exécuter) :

1. Quel est le cas de base de l’algorithme récursif ?

   [Lire]

L’objectif de cette activité est l’écriture d’une fonction qui effectue la rotation d’une image bitmap de 90 degrés en utilisant le principe « Diviser pour régner ».

On peut manipuler des images en Python à l’aide du module PIL (Python Image Library). Une première partie de l’activité est consacrée à la prise en main de ce module. Dans un second temps, la fonction de manipulation des bits est développée.

Images numériques

Définition

Objectifs

Le tri par insertion a été étudié en classe de 1ère. Dans ce document, après un rappel du cours de 1ère, nous allons implémenter une version récursive de cet algorithme et ensuite utiliser la possibilité que les fonctions en Python ont d’accepter des fonctions comme paramètres, afin de rendre plus générale et utile cette fonction de tri.

Tri du joueur de cartes

Tri par insertion

Introduction

La méthode du tri par insertion est ilustré à ici , ou, de façon plus folklorique, ici .

Qu’est-ce que la programmation fonctionnelle ?

S’il n’est pas facile de répondre précisément à cette question, on peut essayer de mettre en évidence les idées que le paradigme fonctionnel promeut :

• Les fonctions doivent être des objets de première classe, c’est à dire que les fonctions doivent pouvoir être passées comme arguments à une fonction, les fonctions doivent aussi pouvoir être retournées par une fonction.

• Les fonctions doivent (le plus possible) être pures, c’est à dire ne générer aucun effet de bord.

  [Lire]

Recherche d’un élément dans un tableau

La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :

• La recherche linéaire itérative ;
• La recherche linéaire récursive ;
• La recherche dichotomique itérative ;
• La recherche dichotomique récursive.

Travail à faire

• Implémenter en Python les cinq algorithmes suivants et répondre aux questions.

Recherche séquentielle (ou linéaire)

Recherche séquentielle itérative

Introduction

Une chaîne de caractère est une structure de données qui permet de rassembler en un unique objet une succession ordonnée de caractères. Ainsi, une définition récursive d’une chaîne de caractères pourrait être :

Une liste est une structure de données qui permet de rassembler en un unique objet une succession ordonnée d’objets (ou de valeurs). Ainsi, une définition récursive d’une liste pourrait être :

La récurrence est un raisonnement mathématique courant et parmi les plus puissants pour démontrer des théorèmes ou construire des objets. Par exemple, on l’utilise dans un cours de mathématique de lycée pour montrer que :

• Pour tout entier $n \geqslant 0$, on a : $1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$ ;
• Un entier naturel n’est autre que 0 ou le successeur d’un entier naturel (0 est 0, 1 est le successeur de 0, 2 est le successeur de 1, …).

En programmation, on peut raisonner de façon identique, nous allons construire des fonctions et des structures de données (listes chaînées, arbres, etc.) à l’aide d’une hypothèse de récurrence et d’un point de départ. Le déroulement de la récurrence sera quant à lui pris en charge par la machine.