La récursion en C

Bonjour à tous, futurs programmeurs ! Aujourd'hui, nous allons plonger dans un des concepts les plus fascinants de la programmation : la récursion. Ne vous inquiétez pas si cela semble intimidant - à la fin de ce tutoriel, vous serez des experts en récursion ! Mettons-nous ensemble sur cette aventure passionnante.

Qu'est-ce qu'une fonction récursive en C ?

Imaginez que vous vous regardez dans un miroir, et derrière vous, il y a un autre miroir. Vous voyez un nombre infini de reflets de vous-même. C'est un peu comme la récursion en programmation !

Une fonction récursive est une fonction qui s'appelle elle-même pendant son exécution. C'est comme une fonction disant : "Hey, j'ai besoin d'aide. Qui de mieux pour me aider que... moi-même ?"

Voici un exemple simple :

void countdown(int n) {
if (n == 0) {
printf("Blastoff!\n");
} else {
printf("%d\n", n);
countdown(n - 1);
}
}

Dans cette fonction, countdown s'appelle avec un nombre plus petit à chaque fois. C'est comme un compte à rebours de fusée, où nous continuons à compter jusqu'à ce que nous atteignions zéro, puis nous décollons !

Pourquoi utiliser la récursion en C ?

Vous pourriez vous demander : "Pourquoi se embêter avec la récursion alors que nous avons des boucles ?" Excellent question ! La récursion a plusieurs avantages :

1. Elle peut rendre le code plus lisible et élégant pour certains problèmes.
2. Elle est parfaite pour les tâches qui ont une nature récursive, comme parcourir des structures en arbre.
3. Elle peut réduire le besoin de structures de boucles complexes et de variables temporaires.

Cependant, la récursion n'est pas toujours le meilleur choix. Elle peut être gourmande en mémoire et plus lente pour certains problèmes. Comme pour beaucoup de choses en programmation, il s'agit de choisir le bon outil pour le travail.

Calcul du factoriel avec la récursion

Regardons un exemple classique de récursion : le calcul des factoriels. Le factoriel d'un nombre n (écrit n!) est le produit de tous les entiers positifs inférieurs ou égaux à n.

Voici comment nous pouvons calculer les factoriels récursivement :

int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

Décomposons cela :

1. Si n est 0 ou 1, nous retournons 1 (c'est notre cas de base).
2. Sinon, nous multiplions n par le factoriel de (n-1).

Donc, si nous appelons factorial(5), voici ce qui se passe :

• 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

Et voilà - 5! = 120.

Recherche binaire avec la récursion

La recherche binaire est un algorithme efficace pour trouver un élément dans une liste triée. Elle fonctionne en divisant régulièrement l'intervalle de recherche par deux. Mettons-la en œuvre récursivement :

int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);
}

return -1;
}

Cette fonction fait ce qui suit :

1. Calcule l'index médian.
2. Si l'élément médian est la cible, c'est terminé !
3. Si la cible est inférieure à l'élément médian, cherchez dans la moitié gauche.
4. Si la cible est supérieure à l'élément médian, cherchez dans la moitié droite.
5. Si nous ne trouvons pas l'élément, retournons -1.

C'est comme un jeu high-tech de "devine le nombre", où vous devinez toujours le nombre médian dans la plage restante !

Séquence de Fibonacci avec la récursion

La séquence de Fibonacci est une série de nombres où chaque nombre est la somme des deux nombres précédents. C'est un candidat parfait pour la récursion !

Voici comment nous pouvons générer les nombres de Fibonacci récursivement :

int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

Cette fonction fonctionne comme suit :

1. Si n est 0 ou 1, nous retournons n (ceux-ci sont nos cas de base).
2. Pour tout autre n, nous retournons la somme des deux nombres de Fibonacci précédents.

Donc, si nous appelons fibonacci(5), voici ce qui se passe :

• fibonacci(5) = fibonacci(4) + fibonacci(3)
• fibonacci(4) = fibonacci(3) + fibonacci(2)
• fibonacci(3) = fibonacci(2) + fibonacci(1)
• fibonacci(2) = fibonacci(1) + fibonacci(0)
• fibonacci(1) = 1
• fibonacci(0) = 0

En travaillant à l'envers, nous obtenons :

• fibonacci(2) = 1 + 0 = 1
• fibonacci(3) = 1 + 1 = 2
• fibonacci(4) = 2 + 1 = 3
• fibonacci(5) = 3 + 2 = 5

Ainsi, le 5ème nombre de Fibonacci est 5 !

Méthodes récursives courantes

Voici un tableau des méthodes récursives courantes que nous avons discutées :

Méthode	Description	Cas de base	Cas récursif
Factoriel	Calcule n!	n = 0 ou 1	n * factorial(n-1)
Recherche binaire	Trouve un élément dans un tableau trié	Élément trouvé ou non dans le tableau	Recherche moitié gauche ou droite
Fibonacci	Génère les nombres de Fibonacci	n <= 1	fibonacci(n-1) + fibonacci(n-2)

Souvenez-vous, la clé pour comprendre la récursion est de faire confiance que l'appel récursif fera correctement son travail. C'est comme déléguer une tâche à un clone de vous-même - vous savez qu'ils la géreront aussi bien que vous !

La récursion peut être un peu déroutante au début, mais avec de la pratique, elle devient un outil puissant dans votre boîte à outils de programmation. Continuez à expérimenter, et bientôt vous trouverez des solutions récursives partout !

Bonne programmation, et souvenez-vous - pour comprendre la récursion, vous devez d'abord comprendre la récursion. ?

Credits: Image by storyset