Fonction récursive

Calculer la suite de Fibonacci

Algorithmique

Je vais t’expliquer ce qu’est une fonction récursive et comment on peut l’utiliser dans un problème réel qui est le calcul de la suite de Fibonacci.

Il s’agira principalement d’algorithmique mais pour illustrer mes propos, je vais utiliser le language PHP.

Une histoire de lapin

La suite de Fibonacci (Fibo pour les intimes) est une suite créée par un célèbre mathématicien italien du même nom. Elle est décrite de la façon suivante : « Un homme met un couple de lapins dans un lieu isolé de tous les côtés par un mur. Combien de couples obtient-on en un an si chaque couple engendre tous les mois un nouveau couple à compter du troisième mois de son existence ? »

Les premiers nombres que l’on trouve : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Alors pour calculer cette suite, je vais utiliser ma propre méthode, mais il en existe des centaines !

Graphique

La première chose que je fais, c’est écrire visuellement la suite au fur et à mesure des mois. 0 est un couple de lapins normal et 1 est un couple de lapins qui peut se reproduire.

//Etat initiale il y a un couple de lapins
0
//Etape 2 le couple de lapins devient fécond
1
//Etape 3 le couple pond un nouveau couple
10
//Etape 4 le couple pond encore un couple et le couple 0 devient un 1 (j'ajoute les couples pondus à la fin)
110
//Etape 5 les deux premiers couples féconds génèrent deux couples et le 0 devient un 1
11100

En additionnant le nombre de 1 de chaque ligne, on obtient les nombres de Fibonacci, donc j’ai bien compris la génération de la suite.

Fonction

Maintenant faisons un peu de code pour afficher les nombres de la suite de Fibo.

Je commence par écrire une fonction et j’ajoute un argument « $etape » qui va définir le nombre d’itération en cours et je fais appel à la fonction en ajoutant comme paramètre l’entier 10.

<?php

	function fibo( $etape ){
		echo "Etape $etape<br/>";		
	}	
	
	fibo( 10 );
	
?>

Récursif

J’ajoute une constante $max_iteration qui elle va correspondre au nombre d’itérations maximal que je veux faire (en gros le nombre d’éléments de la suite que je veux afficher).

Dans ma fonction, je teste si l’étape est plus petite que la valeur de $max_iteration, si c’est le cas alors je relance la fonction fibo (donc dans elle-même, c’est ça la récursivité) avec un nouveau paramètre qui va être l’étape incrémentée de 1.

<?php

	const max_iteration = 10;
	function fibo( $etape ){
		echo "Etape $etape<br/>";
		if( $etape < max_iteration ){
			fibo( $etape+1 );
		}
		
	}	
	
	fibo( 1 );
	
?>

Donc tu l’auras compris, la fonction fibo va s’auto appeler jusqu’à ce que la valeur de $etape soit égale à 10 et va donc afficher :

Etape 1
Etape 2
Etape 3
Etape 4
Etape 5
Etape 6
Etape 7
Etape 8
Etape 9
Etape 10

Tableau des couples

Je crée un tableau (tableau_couple) qui va me permettre de stocker la valeur de chaque couple de lapins avec des 0 et des 1 et dedans le place un premier couple grâce à la valeur 0.

Ensuite j’ajoute ce tableau comme argument de la fonction fibo. A chaque étape j’affiche le tableau et je mets un peu de code HTML pour faciliter la lecture à l’écran.

<?php

	const max_iteration = 10;
	$tableau_couple = array(0);
	function fibo( $etape, $tableau_couple ){
		echo "Etape $etape";
		print_r($tableau_couple);
		echo "<hr/>";
		
		if( $etape < max_iteration ){
			fibo( $etape+1, $tableau_couple );
		}

	}	
	
	fibo( 1, $tableau_couple );
	
?>

Maintenant je dois implanter la logique de calcul de la suite et ce n’est pas compliqué du tout.

A chaque nouvelle étape je parcours l’entièreté du tableau. Si je trouve un couple 0 alors je le transforme en 1 (cas d’un couple qui devient fécond) et si je trouve un 1 alors j’ajoute un 0 (cas d’un couple qui pond).

J’ajoute la boucle for qui me permet de boucler sur chaque élément du tableau et je masque la récursivité pour le moment.

<?php

	const max_iteration = 10;
	$tableau_couple = array(0);
	function fibo( $etape, $tableau_couple ){
		echo "Etape $etape : ";

		$taille_tableau = count($tableau_couple);
		for($i = 0; $i < $taille_tableau; $i++ ){
			echo $tableau_couple[$i];
		}
		
		
		echo "<hr/>";
		/*
		if( $etape < max_iteration ){
			fibo( $etape+1, $tableau_couple );
		}*/

	}	
	
	fibo( 1, $tableau_couple );
	
?>

J’ajoute une variable $couple_etape qui va me permettre d’afficher le nombre de couples à chaque étape.

J’applique les deux changements que j’ai expliqués au dessus à chaque passage dans la boucle for.

Pour respecter le 0 initial de la suite, j’incrémente $couple_etape seulement lorsqu’il y a un couple fécond et je lance la fonction fibo avec l’étape 0 au lancement de la fonction.

<?php

	const max_iteration = 10;
	$tableau_couple = array(0);
	function fibo( $etape, $tableau_couple ){
		echo "Etape $etape : ";

		$couple_etape = 0;
		$taille_tableau = count($tableau_couple);
		for($i = 0; $i < $taille_tableau; $i++ ){
			if( $tableau_couple[$i] == 0 ){
				$tableau_couple[$i] = 1;
			}elseif( $tableau_couple[$i] == 1 ){
				$tableau_couple[] = 0;
				$couple_etape++;
			}
		}
		
		echo $couple_etape . "<br/>";

		if( $etape < max_iteration ){
			fibo( $etape+1, $tableau_couple );
		}

	}	
	
	fibo( 0, $tableau_couple );
	
?>

Et le tour est joué :

Etape 0 : 0
Etape 1 : 1
Etape 2 : 1
Etape 3 : 2
Etape 4 : 3
Etape 5 : 5
Etape 6 : 8
Etape 7 : 13
Etape 8 : 21
Etape 9 : 34
Etape 10 : 55

L’avantage de travailler avec un tableau, c’est que je peux directement faire référence à l’exemple graphique, donc c’est super facile à comprendre. Un autre avantage est que je peux stocker le calcul, c’est-à-dire sauvegarder la dernière clé/valeur et le reprendre là où je me suis arrêté, dans le cas où je voudrais calculer encore plus de chiffres de cette suite !

11/08/2018

Yann Vangampelaere - nouslesdevs -

Sinon jete un coup d’oeil aux autres catégories

Ma boîte aux lettres

Tu veux me demander quelque chose ?