Introduction


Les points abordés dans ce TP sont :

• la récursivité
• les définitions par récurrence
• la relation entre récursivité et itération
• les fractales
• l'exploration arborescente

Ce qui est à faire :

• La fonction 91 de MacCarthy est définie ainsi, pour tout n un entier naturel :
  

       f91(n) = n-10           si n>100
       f91(n) = f91(f91(n+11)) si n<=100
  

  Définir cette fonction en C et écrire un petit programme qui affiche les valeurs de cette fonction pour n <= 101.

• Retour sur le Triangle de Pascal (cf. TP 8) :

  On rappelle que la n-ième ligne de ce triangle contient les n+1 coefficients C(n,p) (0<=p<=n) du binôme (a+b)^n
  et que ces coefficients vérifient la relation C(n,p) = C(n-1,p-1) + C(n-1,p).
  

  Définir une fonction C qui calcule le coefficient C(n,p) étant données n et p.
  Utiliser cette fonction pour écrire une autre version du programme qui affiche
  les N premières lignes du Triangle de Pascal où N est une constante définie dans le programme.

Reprendre certaines fonctions de manipulation des chiffres d'un entier naturel du TP 5 et
en donner une définition récursive. Ecrire un programme pour les tester :
• Nombre de chiffres d'un nombre entier.
• ième chiffre d'un nombre entier. Ex: le 1er chiffre de 421 est 4, le 2éme est 2 et le 3ème est 1.
• Inversion des chiffres. Ex: 1234 devient 4321 (700 devient simplement 7).
• Somme des chiffres. Ex: la somme des chiffres de 1234 est 1+2+3+4 = 10.

Des exemples spectaculaires de fonctions récursives sont les fonctions graphiques de dessin de fractales.
• Flocon de von Koch : Un premier exemple est le flocon de von Koch défini comme suit :
  

      

  • Le flocon d'ordre 0 est un triangle équilatéral.
  • Le flocon d'ordre 1 est ce même triangle dont les côtés sont découpés en trois et
    sur lequel s'appuie un autre triangle équilatéral au milieu.
  • Le flocon d'ordre n+1 consiste à prendre le flocon d'ordre n
    en appliquant la même opération sur chacun de ses côtés.
    
    Le résultat ressemble effectivement à un flocon de neige idéalisé.
    

  Ecrire un programme de dessin du flocon de von Koch d'ordre n.
  On utilisera les fonctions trigonométriques sin et cos de la bibliothèque des fonctions mathématiques.
  

• Courbe du Dragon : Un autre exemple classique est la courbe du Dragon définie comme suit :
  
  • la courbe du Dragon d'ordre 1 est un vecteur entre deux points quelconques A et B,
    
  • la courbe du Dragon d'ordre n est la courbe du Dragon d'ordre n-1 entre A et M
    suivie de la même courbe d'ordre n-1 entre M et B (à l'envers),
    où (AMB) est le triangle isocèle rectangle en M, et M est à droite du vecteur AB.
    Donc, si A et B sont les points de coordonnées (xA, yA) et (xB,yB), les coordonnées (x,y) de M sont :
    x = (xA + xB)/2 + (yB - yA)/2
    y = (yA + yB)/2 - (xB - xA)/2
    

  Ecrire un programme de dessin de la courbe du Dragon.

Pour certain problème, trouver une solution consiste à explorer toutes les possibilités.
La récursivité peut être d'une aide précieuse. Voici deux exemples inspirés du jeu d'échecs.
On utilisera un tableau à 2 dimensions pour représenter l'échiquier de 8 cases de cotés.
Pour chacun des 2 exemples, il s'agit d'écrire un programme C qui résoud le problème posé.
• Le problème des 8 reines : Placer 8 reines sur un échiquier de sorte qu'aucune reine ne soit en prise :
  il ne faut donc pas plus d'une reine par ligne, par colonne et par diagonale.
  

• Le problème du cavalier : Connaissant la position initiale d'un cavalier sur un échiquier,
  trouver un parcours de ce cavalier tel que celui-ci visite l'ensemble des cases de l'échiquier
  sans passer une seule fois sur une case déja visitée. Partant d'une case donnée,
  le cavalier peut atteindre en un déplacement 8 cases au maximum comme le montre la figure ci-dessous :