Programmation récursive

Présentation

On dit qu'une fonction est récursive si elle s'appelle elle même.

exemple

Considérons la multiplication 5 × 101, j’espère que vous savez tous que cela fait 505, pour tant vous n'avez pas appris les multiplications jusqu’à 101, vous faites (sans le savoir peut être) 5 × (100 + 1) = 5 × 100 + 5 = 500 + 5 = 505. Si jamais vous connaissez une multiplication par n alors il n'y a pas de problème pour multiplier par n+1, par exemple comme 5 × 13 = 65 alors 5 × 14 = .... utilisons cette propriété pour programmer de manière récursive la multiplication.


		
Dans l'exemple ci dessous à chaque fois que l'on utilise la fonction un message apparait, rendez vous compte que la fonction s'appelle de nombreuses fois.

		
 
		

		
 

		 

		

		

		
 
		

		
La programmation récursive peut avoir de nombreux avantages, la clareté d'abord, la simplicité (voir tour de Hanoi), la possibilité d'éviter les effets de bord (modification des variables), la programmation récursive est très utilisée en programmation fonctionnelle (langage Ocaml ou Haskell par exemple).

		
La programmation a aussi des défauts, dans certains cas les performances mémoires et/ou les performances sont catastrophiques, examinons un grand classique des mathématiques, la suite de Fibbonacci :

		
exemple
		
 Compléter la suite logique 1 - 1 - 2 - 3 - 5 - 8 - 13 - 21 - ... - ... - ...

	
		
La suite de nombres précédents est appellée suite de fibbonacci, elle est définie pour n entier naturel par u0 = 1, u1 = 1 et la relation de récurrence un+2 =   un+1 +  un, historiquement la suite permet de répondre à un exercice sur la reproduction des lapins, elle fait apparaître le nombre d'or.

		
Voici trois facons de la programmer :

		

		
Dans l'exemple ci dessous à chaque fois que l'on utilise la fonction récursive un message apparait.

		
 
		

		
 

		 

		
 

		

		
Remarquez que la fonction fait plein de fois les mêmes calculs.
Pour la calcul de u4 voici l'ensemble des calculs sous la forme d'un arbre :

		
		

		
exemple
		
Le grand classique de la programmation récursive est celui de la résolution des tours de Hanoi, le but du jeu est de transférer les disques du pilier 1 au pilier 3 sauf que l'on ne peut déplacer qu'un disque à la fois et de plus on ne peut poser un disque que sur un disque de rayon plus grand.

		
Vous pouvez essayer sur le dessin suivant :

		

		
On peut se dire que c'est dur de programmer la résolution, mais il "suffit" de le voir en trois parties :

		
		

		
		

		
exemple
		
Quand on travaille sur les listes la récurrence se fait sur la longueur de la liste, voici deux façons de programmer la rechercher du maximum d'une liste par récurrence, la première manière est plus performante mais demande d'avoir deux paramètres.

		

		

		
Si on veut chercher l'élément maximum du tableau :

		
2413

		
On cherche le plus grand élément des trois premiers éléments :

		
241

		
qui est 4, et on le compare avec le dernier élément du tableau qui est 3.

		

		

		
exemple
		
    
			
  1. On veut calculer la somme des n premiers entiers en version récursive S(n) = 0 + 1 + 2 + 3 + ... + n.
    
				
      
				
    1. Condition d'arret si n = 0 alors S(0) = ...  (Compléter les ...)
      2. 
				
    2. Relation de récurrence si n > 0, S(n) = S(n-1) + ... 
      3. 
				
    3. Programmer la somme en version récursive.
      4. 
				
    
			
    2. 
			
  2. On veut calculer la factorielle en version récursive n ! = 1 × 2 × ... × (n-1) × n. Par convention 0 ! = 1
    
				
      
				
    1. Condition d'arret si n = ... alors (...) ! = ...  (Compléter les ...).
      2. 
				
    2. Relation de récurrence si n > ... alors n ! = (n-1) ! × ... .
      3. 
				
    3. Programmer la factorielle en version récursive (on appelera la fonction fact).
      4. 
				
    
			
    3. 
			
  3. On veut calculer par récursivité la somme des éléments d'une liste par exemple somme([ 2, 3, 4]) = 9, la récurence s'applique généralement sur la longueur de la liste.
    
			
      
			
    1. Condition d'arret si len(l) = 0 alors somme(l) = ...
      2. 
			
    2. Relation de récurrence somme(l) = somme(l[:-1]) + ...
      3. 
			
    3. Programmer la somme de maniére récursive.
      4. 
			
    
			
  4. On veut calculer la puissance n d'un nombre a (n est entier positif) :
			
      
			
    1. Condition d'arret si n = 0 alors puis(a,n) = ...
      2. 
			
    2. Relation de récurrence puis(a,n) = ...
      3. 
			
    3. Programmer la somme de maniére récursive.
      4. 
			
    
			
  5. On a un tableau d'entier, faire une fonction récursive qui donne le nombre d'entier pair du tableau.
    6. 
			
  6. Écrire une fonction récursive qui va afficher les nombres entiers consécutifs, exemple consecutif(5) = 1 2 3 4 5. Si on utilise print(a) alors on va à la ligne sauf si on donne explicitement le caractère final (qui par défaut est "\n" à la ligne, print(a,end = " ") va afficher a et ne va pas aller à la ligne.
    7. 
			
  7. Ecrire une fonction récursive qui va afficher les nombres entiers consécutifs mais à l'envers, exemple consecutif_envers(5) = 5 4 3 2 1.
    8.