PHP - Fonctions Récurrentes

Salut à toi, aspirant.e.s programmeur.euse.s ! Aujourd'hui, nous allons plonger dans le monde fascinant des fonctions récurrentes en PHP. Ne t'inquiète pas si tu es nouveau.e dans la programmation ; je vais te guider pas à pas à travers ce concept, tout comme j'ai fait pour des centaines d'étudiant.e.s au fil des ans. Alors, prends une tasse de café (ou ton breuvage préféré), et rejoins-moi dans cette aventure passionnante !

PHP - Recursive Functions

Quelles sont les Fonctions Récurrentes ?

Avant de rentrer dans les détails, comprenons ce qu'are les fonctions récurrentes. Imagine que tu te regardes dans un miroir, et qu'il y a un autre miroir derrière toi. Tu vois une réflexion infinie de toi-même, n'est-ce pas ? C'est un peu comme ça que fonctionnent les fonctions récurrentes en programmation !

Une fonction récurrente est une fonction qui s'appelle elle-même pendant son exécution. C'est comme une version numérique des poupées russes, où chaque poupée contient une version plus petite d'elle-même à l'intérieur.

Pourquoi Utiliser des Fonctions Récurrentes ?

Tu te demandes peut-être : "Pourquoi voudrais-je qu'une fonction s'appelle elle-même ? Ça ne risque-t-il pas de être confus ?" Eh bien, les fonctions récurrentes peuvent être extrêmement utiles pour résoudre des problèmes qui ont une structure répétitive. Elles peuvent rendre notre code plus élégant et plus facile à comprendre pour certains types de problèmes.

Regardons un exemple simple pour nous mettre en jambe :

function countDown($n) {
if ($n <= 0) {
echo "Blastoff!";
} else {
echo $n . "... ";
countDown($n - 1);
}
}

countDown(5);

Si nous exécutons cette fonction avec countDown(5), voici ce qui se passe :

  1. Elle affiche "5... "
  2. Ensuite, elle s'appelle elle-même avec 4
  3. Affiche "4... "
  4. S'appelle elle-même avec 3
  5. Et ainsi de suite jusqu'à ce qu'elle atteigne 0 et affiche "Blastoff!"

La sortie serait : "5... 4... 3... 2... 1... Blastoff!"

L'Anatomie d'une Fonction Récurrente

Chaque fonction récurrente comporte deux parties principales :

  1. Cas de base : C'est la condition qui arrête la récursion. Sans elle, ta fonction s'appellerait elle-même indéfiniment (ou jusqu'à ce que ton ordinateur se fatigue de la mémoire) !

  2. Cas récurrent : C'est où la fonction s'appelle elle-même, généralement avec un paramètre modifié.

Dans notre exemple de countdown, if ($n <= 0) est le cas de base, et countDown($n - 1) est le cas récurrent.

Calcul du Factoriel par Récursion

Maintenant que nous avons les bases, abordons un problème classique : le calcul des factoriels. Le factoriel d'un nombre n (noté n!) est le produit de tous les entiers positifs inférieurs ou égaux à n.

Par exemple : 5! = 5 4 3 2 1 = 120

Voici comment nous pouvons calculer les factoriels en utilisant la récursion :

function factorial($n) {
if ($n <= 1) {
return 1;
} else {
return $n * factorial($n - 1);
}
}

echo factorial(5); // Output: 120

Décomposons cela :

  1. Notre cas de base est if ($n <= 1). Nous savons que 1! et 0! sont tous deux égaux à 1, donc nous retournons 1 dans ce cas.
  2. Pour tout autre nombre, nous multiplions $n par le factoriel de (n-1).

Lorsque nous appelons factorial(5), voici ce qui se passe en arrière-plan :

factorial(5) = 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

Ce n'est pas magnifique comment la fonction continue de s'appeler elle-même jusqu'à atteindre le cas de base, et puis les résultats remontent ?

Recherche Binaire par Récursion

Maintenant, levons le niveau et regardons un exemple plus complexe : la recherche binaire. La recherche binaire est un algorithme efficace pour trouver un élément dans une liste triée. Elle fonctionne en divisant régulièrement par deux la portion de la liste qui pourrait contenir l'élément, jusqu'à ce que tu aies réduit les emplacements possibles à un seul.

Voici comment nous pouvons implémenter la recherche binaire en utilisant la récursion :

function binarySearch($arr, $left, $right, $x) {
if ($right >= $left) {
$mid = $left + floor(($right - $left) / 2);

// Si l'élément est présent au milieu lui-même
if ($arr[$mid] == $x) {
return $mid;
}

// Si l'élément est plus petit que mid, alors il ne peut être présent que dans le sous-tableau de gauche
if ($arr[$mid] > $x) {
return binarySearch($arr, $left, $mid - 1, $x);
}

// Sinon, l'élément ne peut être présent que dans le sous-tableau de droite
return binarySearch($arr, $mid + 1, $right, $x);
}

// Nous en arrivons ici lorsque l'élément n'est pas présent dans le tableau
return -1;
}

$arr = [2, 3, 4, 10, 40];
$x = 10;
$result = binarySearch($arr, 0, count($arr) - 1, $x);
echo ($result == -1) ? "Élément absent du tableau" : "Élément présent à l'index " . $result;

Cette fonction peut sembler intimidante au premier abord, mais analysons-la :

  1. Nous vérifions si l'index de droite est supérieur ou égal à l'index de gauche. C'est notre condition de continuation.
  2. Nous calculons l'index du milieu.
  3. Si l'élément du milieu est notre cible, nous y sommes !
  4. Si l'élément du milieu est plus grand que notre cible, nous cherchons récursivement dans la moitié gauche du tableau.
  5. Si l'élément du milieu est plus petit que notre cible, nous cherchons récursivement dans la moitié droite du tableau.
  6. Si nous avons épuisé notre recherche (droite < gauche), nous retournons -1 pour indiquer que l'élément n'a pas été trouvé.

La beauté de cette approche récursive est comment elle divise naturellement le problème en sous-problèmes plus petits, rendant le code élégant et facile à comprendre une fois que tu as saisi le concept.

Conclusion

Les fonctions récurrentes peuvent sembler un peu tordues au début, mais elles sont un outil incroyablement puissant dans la boîte à outils d'un.e programmeur.euse. Elles nous permettent de résoudre des problèmes complexes avec un code élégant et concis. Plus tu pratiques, plus tu commenceiras à reconnaître les problèmes qui se prêtent bien à des solutions récurrentes.

N'oublie pas, comme avec tout outil puissant, la récursion doit être utilisée avec discernement. Parfois, une solution itérative pourrait être plus efficace ou plus facile à comprendre. À mesure que tu gagnes en expérience, tu développeras une intuition pour savoir quand utiliser la récursion et quand utiliser d'autres approches.

Continue de coder, continue d'expérimenter, et surtout, amuse-toi ! La programmation est à la fois un art et une science, et maîtriser des concepts comme la récursion te aidera à créer du code beau et efficace. Jusqu'à la prochaine fois, bon codage !

Méthode Description Exemple
countDown() Compte à rebours à partir d'un nombre donné jusqu'à zéro countDown(5)
factorial() Calcule le factoriel d'un nombre donné factorial(5)
binarySearch() Recherche un élément dans un tableau trié binarySearch($arr, 0, count($arr) - 1, $x)

Credits: Image by storyset