Documentation du code et tests



		


Récursivité


Définition : une fonction récursive est une fonction qui s'appelle elle-même.

Exemples de fonctions récursives en Python
La fonction factorielle


				

La suite de Fibonacci


				

Rendu de pièces (algorithme glouton)


				

Figure géométrique dessinée avec le module Turtle

				

Listes - Piles - Files


Les listes

Une liste est une structure de données permettant de regrouper des données et dont l'accès est séquentiel.

Opérations sur une liste :

Représentation d'une liste avec un tableau L[0..n]:

Représentation d'une liste de taille maximale 5 éléments.
Les piles

Les piles sont basées sur le principe LIFO (Last In First Out : le dernier rentré sera le premier à sortir). On retrouve souvent ce principe LIFO en informatique.

Opérations sur une pile :

Représentation d'une pile avec un tableau P[0..n]
  • La première case du tableau (d'indice 0) contient l'indice de la prochaine case vide.
  • Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la pile ou bien sont vides. La dernière case non vide du tableau est le sommet de la pile.
  • Représentation d'une liste de taille maximale 5 éléments.
    Les files
    File

    Les files sont basées sur le principe FIFO (First In First Out : le premier qui est rentré sera le premier à sortir.

    Opérations sur une file :

    Représentation d'une file avec un tableau F[0..n+2]

    les arbres


    Un arbre est une structure de données constituée de noeuds qui peuvent avoir comme enfants d'autres noeuds.

    Vocabulaire
    Caractéristiques
    Arbres binaires

    Les arbres binaires ont au plus deux enfants. L'arité d'un arbre binaire est 2.

    Cas particuliers d'arbres binaires

    Mesures sur les arbres binaires
    Arbres binaires de recherche

    Un arbre binaire de recherche est un arbre défini comme suit :

    Kiwi standing on oval
    Cas particulier d'arbres binaires de recherche : les arbres équilibrés

    Un arbre équilibré est un arbre binaire de recherche qui maintient une profondeur équilibrée entre ses branches. La différence de longueur entre sa branche la plus longue et la branche la moins longue est au plus égale à 1.)

    Type abstrait Arbre

    Un arbre peut être construit sur des éléments de type N de manière récursive de la manière suivante :

    Voici les opérations qui peuvent être effectuées sur un arbre