Fonction récursive en C : Exercices Corrigés
La programmation récursive est une technique où une fonction s’appelle elle-même pour résoudre un problème. Cette approche est particulièrement utile pour les problèmes qui peuvent être décomposés en sous-problèmes similaires. En langage C, la récursivité est un concept puissant mais doit être utilisé avec précaution pour éviter les erreurs telles que les débordements de pile.
Structure d’une fonction récursive
Pour qu’une fonction récursive soit correctement implémentée, elle doit comporter deux éléments clés :
- Cas de base : une condition qui met fin à la récursivité.
- Appel récursif : la fonction s’appelle elle-même avec des arguments modifiés, rapprochant ainsi la solution du cas de base.
Exemple de base : Factorielle
La fonction factorielle d’un nombre ( n ) (notée ( n! )) est un exemple classique de récursion. Voici comment on peut l’implémenter en C :
#include <stdio.h>
int factorielle(int n) {
if (n <= 1) {
return 1;
} else {
return n * factorielle(n - 1);
}
}
int main() {
int nombre = 5;
printf("La factorielle de %d est %d\n", nombre, factorielle(nombre));
return 0;
}Exercices corrigés
Voici une série de 16 exercices corrigés pour approfondir la compréhension des fonctions récursives en C.
Exercice 1 : Somme des entiers de 1 à n
Énoncé : Écrire une fonction récursive qui calcule la somme des entiers de 1 à ( n ).
Correction :
#include <stdio.h>
int somme(int n) {
if (n == 1) {
return 1;
} else {
return n + somme(n - 1);
}
}
int main() {
int nombre = 10;
printf("La somme des entiers de 1 à %d est %d\n", nombre, somme(nombre));
return 0;
}Exercice 2 : Série de Fibonacci
Énoncé : Écrire une fonction récursive pour générer le ( n )-ième terme de la série de Fibonacci.
Correction :
#include <stdio.h>
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main() {
int terme = 6;
printf("Le %d-ième terme de la série de Fibonacci est %d\n", terme, fibonacci(terme));
return 0;
}Exercice 3 : Calcul de la puissance
Énoncé : Écrire une fonction récursive pour calculer ( x ) élevé à la puissance ( y ) ( ( x^y ) ).
Correction :
#include <stdio.h>
int puissance(int x, int y) {
if (y == 0) {
return 1;
} else {
return x * puissance(x, y - 1);
}
}
int main() {
int base = 2, exposant = 3;
printf("%d à la puissance %d est %d\n", base, exposant, puissance(base, exposant));
return 0;
}Exercice 4 : Inverser une chaîne de caractères
Énoncé : Écrire une fonction récursive pour inverser une chaîne de caractères.
Correction :
#include <stdio.h>
#include <string.h>
void inverser(char *str, int debut, int fin) {
if (debut >= fin) {
return;
}
char temp = str[debut];
str[debut] = str[fin];
str[fin] = temp;
inverser(str, debut + 1, fin - 1);
}
int main() {
char chaine[] = "recursion";
inverser(chaine, 0, strlen(chaine) - 1);
printf("Chaîne inversée : %s\n", chaine);
return 0;
}Exercice 5 : Nombre de chiffres
Énoncé : Écrire une fonction récursive pour compter le nombre de chiffres d’un entier.
Correction :
#include <stdio.h>
int compte_chiffres(int n) {
if (n == 0) {
return 0;
} else {
return 1 + compte_chiffres(n / 10);
}
}
int main() {
int nombre = 12345;
printf("Le nombre de chiffres dans %d est %d\n", nombre, compte_chiffres(nombre));
return 0;
}Exercice 6 : Somme des chiffres
Énoncé : Écrire une fonction récursive pour calculer la somme des chiffres d’un entier.
Correction :
#include <stdio.h>
int somme_chiffres(int n) {
if (n == 0) {
return 0;
} else {
return (n % 10) + somme_chiffres(n / 10);
}
}
int main() {
int nombre = 12345;
printf("La somme des chiffres de %d est %d\n", nombre, somme_chiffres(nombre));
return 0;
}Exercice 7 : Recherche d’un élément dans un tableau
Énoncé : Écrire une fonction récursive pour rechercher un élément dans un tableau.
Correction :
#include <stdio.h>
int recherche(int arr[], int taille, int element) {
if (taille == 0) {
return -1;
} else if (arr[taille - 1] == element) {
return taille - 1;
} else {
return recherche(arr, taille - 1, element);
}
}
int main() {
int tableau[] = {2, 4, 6, 8, 10};
int taille = sizeof(tableau) / sizeof(tableau[0]);
int element = 6;
int index = recherche(tableau, taille, element);
if (index != -1) {
printf("Élément %d trouvé à l'index %d\n", element, index);
} else {
printf("Élément %d non trouvé\n", element);
}
return 0;
}Exercice 8 : Calcul de la somme des éléments d’un tableau
Énoncé : Écrire une fonction récursive pour calculer la somme des éléments d’un tableau.
Correction :
#include <stdio.h>
int somme_tableau(int arr[], int taille) {
if (taille == 0) {
return 0;
} else {
return arr[taille - 1] + somme_tableau(arr, taille - 1);
}
}
int main() {
int tableau[] = {2, 4, 6, 8, 10};
int taille = sizeof(tableau) / sizeof(tableau[0]);
printf("La somme des éléments du tableau est %d\n", somme_tableau(tableau, taille));
return 0;
}Exercice 9 : Trouver le maximum dans un tableau
Énoncé : Écrire une fonction récursive pour trouver le maximum dans un tableau.
Correction :
#include <stdio.h>
int maximum(int arr[], int taille) {
if (taille == 1) {
return arr[0];
} else {
int max = maximum(arr, taille - 1);
return (arr[taille - 1] > max) ? arr[taille - 1] : max;
}
}
int main() {
int tableau[] = {2, 4, 6, 8, 10};
int taille = sizeof(tableau) / sizeof(tableau[0]);
printf("Le maximum du tableau est %d\n", maximum(tableau, taille));
return 0;
}Exercice 10 : Tri à bulle récursif
Énoncé : Écrire une fonction récursive pour trier un tableau en utilisant le tri à bulle.
Correction :
#include <stdio.h>
void echanger(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void tri_bulle(int arr[], int taille) {
if (taille == 1) {
return;
}
for (int i = 0; i < taille - 1; i++) {
if (arr[i] > arr[i + 1]) {
echanger(&arr[i], &arr[i + 1]);
}
}
tri_bulle(arr, taille - 1);
}
int main() {
int tableau[] = {10, 9, 8, 7, 6};
int taille = sizeof(tableau) / sizeof(tableau[0]);
tri_bulle(tableau, taille);
printf("Tableau trié : ");
for (int i = 0; i < taille; i++) {
printf("%d ", tableau[i]);
}
printf("\n");
return 0;
}Exercice 11 : Convertir un entier en binaire
Énoncé : Écrire une fonction récursive pour convertir un entier en binaire.
Correction :
#include <stdio.h>
void convertir_binaire(int n) {
if (n == 0) {
return;
}
convertir_binaire(n / 2);
printf("%d", n % 2);
}
int main() {
int nombre = 10;
printf("Le binaire de %d est ", nombre);
convertir_binaire(nombre);
printf("\n");
return 0;
}Exercice 12 : Calcul de la moyenne des éléments d’un tableau
Énoncé : Écrire une fonction récursive pour calculer la moyenne des éléments d’un tableau.
Correction :
#include <stdio.h>
float somme_elements(float arr[], int taille) {
if (taille == 0) {
return 0;
} else {
return arr[taille - 1] + somme_elements(arr, taille - 1);
}
}
float moyenne(float arr[], int taille) {
return somme_elements(arr, taille) / taille;
}
int main() {
float tableau[] = {2.0, 4.0, 6.0, 8.0, 10.0};
int taille = sizeof(tableau) / sizeof(tableau[0]);
printf("La moyenne des éléments du tableau est %.2f\n", moyenne(tableau, taille));
return 0;
}Exercice 13 : Trouver le nombre d’occurrences d’un élément dans un tableau
Énoncé : Écrire une fonction récursive pour trouver le nombre d’occurrences d’un élément dans un tableau.
Correction :
#include <stdio.h>
int occurrences(int arr[], int taille, int element) {
if (taille == 0) {
return 0;
} else {
int count = (arr[taille - 1] == element) ? 1 : 0;
return count + occurrences(arr, taille - 1, element);
}
}
int main() {
int tableau[] = {2, 4, 6, 8, 4, 10};
int taille = sizeof(tableau) / sizeof(tableau[0]);
int element = 4;
printf("Le nombre d'occurrences de %d est %d\n", element, occurrences(tableau, taille, element));
return 0;
}Exercice 14 : Trouver la somme des éléments pairs d’un tableau
Énoncé : Écrire une fonction récursive pour trouver la somme des éléments pairs d’un tableau.
Correction :
#include <stdio.h>
int somme_pairs(int arr[], int taille) {
if (taille == 0) {
return 0;
} else {
int sum = (arr[taille - 1] % 2 == 0) ? arr[taille - 1] : 0;
return sum + somme_pairs(arr, taille - 1);
}
}
int main() {
int tableau[] = {2, 4, 6, 8, 10};
int taille = sizeof(tableau) / sizeof(tableau[0]);
printf("La somme des éléments pairs du tableau est %d\n", somme_pairs(tableau, taille));
return 0;
}Exercice 15 : Trouver la profondeur maximale d’un arbre binaire
Énoncé : Écrire une fonction récursive pour trouver la profondeur maximale d’un arbre binaire.
Correction :
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
int profondeur_max(struct Node* node) {
if (node == NULL) {
return 0;
} else {
int left_depth = profondeur_max(node->left);
int right_depth = profondeur_max(node->right);
return (left_depth > right_depth) ? (left_depth + 1) : (right_depth + 1);
}
}
struct Node* nouveauNoeud(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
struct Node* root = nouveauNoeud(1);
root->left = nouveauNoeud(2);
root->right = nouveauNoeud(3);
root->left->left = nouveauNoeud(4);
root->left->right = nouveauNoeud(5);
printf("La profondeur maximale de l'arbre binaire est %d\n", profondeur_max(root));
return 0;
}Exercice 16 : Vérifier si une chaîne est un palindrome
Énoncé : Écrire une fonction récursive pour vérifier si une chaîne est un palindrome.
Correction :
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool est_palindrome(char *str, int debut, int fin) {
if (debut >= fin) {
return true;
}
if (str[debut] != str[fin]) {
return false;
}
return est_palindrome(str, debut + 1, fin - 1);
}
int main() {
char chaine[] = "radar";
if (est_palindrome(chaine, 0, strlen(chaine) - 1)) {
printf("%s est un palindrome\n", chaine);
} else {
printf("%s n'est pas un palindrome\n", chaine);
}
return 0;
}Conclusion
Les fonctions récursives offrent une méthode élégante et efficace pour résoudre divers problèmes de programmation. Bien que la récursion puisse être plus intuitive pour certains problèmes, il est important de comprendre ses limitations, notamment en termes de consommation de mémoire et de temps d’exécution. Les exercices corrigés ci-dessus devraient fournir une base solide pour approfondir la maîtrise de la récursion en C.
Autres articles
