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.
Pour qu’une fonction récursive soit correctement implémentée, elle doit comporter deux éléments clés :
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;
}
Voici une série de 16 exercices corrigés pour approfondir la compréhension des fonctions récursives en C.
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
É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;
}
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.
Définition de la culture d’entreprise La culture d’entreprise désigne l’ensemble des valeurs, croyances, comportements, rites…
La maîtrise de la sécurité alimentaire repose sur une application rigoureuse de méthodes reconnues, dont…
1. Comptabilité analytique (ou de gestion)La comptabilité analytique est un système d’analyse interne qui permet…
Aborder la comptabilité analytique pour la première fois représente un véritable tournant dans la carrière…
La réussite d’un projet repose sur une coordination efficace des tâches, une allocation équilibrée des…
Dans le cadre de la mise en œuvre d'un Système de Management de la Qualité…
This website uses cookies.