TD4 - La récursivité

La récursivité

Durée : 1h30

Inès de Courchelle

Objectifs :

  • Comprendre les mécaniques de la récursivité
  • Développer des algorithmes récursifs

Attention :

À chaque étape de programmation, vous devez vérifier si le programme :

  • Compile sans warning
  • Obtient les résultats attendus
  • Avant de coder, il faut écrire un algo avec un papier et un stylo !

0- Avant de commencer

Dans le répertoire “INFO2”, ajouter le répertoire “TP4”

Exercice 1 : Somme des chiffres

Écrire une fonction récursive qui retourne la somme des chiffres d’un nombre composé de n chiffres. Exemple : sommeChiffre(2195) = 2+1+9+5 = 17

Programme attendu :

Etape 1 : Création du fichier sommeTer.c

  • pour cette exercice inutile de réaliser des fichiers de compilation séparée !
#include <stdlib.h>
#include <stdio.h>

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ... */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int sommeTer(int nb,int acc);

int main(){
    printf("Création du fichier sommeTer.c \n");
    return 0;
}

Etape 2 : Je vérifie qu’il compile et qu’il s’exécute correctement !

gcc -Wall sommeTer.c -o sommeTer
./sommeTer

Etape 3 : Je prends un brouillon, les notes que j’ai pris pendant le TD papier et je réfléchis !

Exercice 2 : Palindrome

Un palindrome est une chaîne de caractères qui se lit de gauche à droite ou de droite à gauche, comme “kayak”, “radar”, “elle”, ou “été”.

  1. Écrire un prédicat récursif qui indique si un mot simple est un palindrome.
  2. Écrire un prédicat récursif qui indique si une phrase est un palindrome. **attention*:
  • il faudra gérer l’espace (‘\0’)
  • il faudra gérer le retour chariot, le retour à la ligne \n
  • il faudra préférer le fgets au scanf

Programme attendu :

Etape 1 : Création du fichier palindrome.c

#include <stdlib.h>
#include <stdio.h>
#define MAX 100

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ... */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int estPalindromeMot(char monMot[MAX],int deb,int fin);

int main(){
    printf("Création du fichier palindrome.c \n");
    return 0;
}
Rappel
  1. En C, il n’y a pas de type Booleen. Vous devez utiliser 0 et 1.
  • 0 => Faux
  • 1 => Vrai
  1. La procédure pour vider le buffer
/* Auteur : Peio L. */
/* Date :  19/11/2022 */
/* Résumé : procédure qui vide le buffer après une saisie */
/* Entrée(s) :  none */
/* Sortie(s) :  none */
void emptyBuffer(){
  char c;
  while (((c = getchar()) != '\n') && (c != EOF));
}
  1. Comment utiliser fgets ? attention ne pas oublier de vider le buffer
#include <stdio.h>
#include <stdlib.h>

int main(){
  char maPhrase[100];
  printf("Entrez la phrase : \n");
  fgets(maPhrase,sizeof(char)*100,stdin);
  return 0;
}
  1. Comment connaître la taille d’une chaîne de caractères ?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    int taille;
    printf("Entrez la phrase : \n");
    fgets(maPhrase,sizeof(char)*100,stdin);
    taille=strlen(maPhrase)-1;
    printf("La taille de maPhrase est %ld \n",taille);
    return 0;
}

Etape 2 : Je vérifie qu’il compile et qu’il s’exécute correctement !

gcc -Wall palindrome.c -o palindrome
./palindrome

Etape 3 : Je prends un brouillon, les notes que j’ai pris pendant le TD papier et je réfléchis !

Etape 4 : Je rajoute la fonction est estPalindromePhrase

#include <stdlib.h>
#include <stdio.h>
#define MAX 100

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ... */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int estPalindromeMot(char monMot[MAX],int deb,int fin);


/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ... */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int estPalindromePhrase(char maPhrase[MAX],int deb,int fin);


int main(){
 /* Le code que j'ai écris avant */
 /* ..... */
 return 0;
}

Exercice 3 : Supprimer un caractère

Écrire une fonction suppCar(ch: chaîne, c: caractère): chaîne qui permet de “supprimer” un caractère d’une chaîne de caractères.

Programme attendu :

Etape 1 : Création du fichier supprimerCar.c

#include <stdlib.h>
#include <stdio.h>
#define MAX 100

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ... */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
void supprCar(char maPhraseInitiale[MAX],char car,int i,int j, char maPhraseModifiee[MAX]);

int main(){
    printf("Création du fichier supprimerCar.c \n");
    return 0;
}

Etape 2 : Je vérifie qu’il compile et qu’il s’exécute correctement !

gcc -Wall supprimerCar.c -o supprimerCar
./supprimerCar

Etape 3 : Je prends un brouillon, et je réfléchis !

Exercice 4 : La puissance

  1. Écrire une fonction récursive non terminale pour calculer a à la puissance b
/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ... */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int puissanceRec (int a, int b);
  1. Écrire une fonction récursive terminale pour calculer a à la puissance b
/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ... */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int puissanceRecTerminale (int a, int b, int acc);

Exercice 5 : Le complet

  1. Créer les fichiers suivants :

  1. Dans les fichiers fonctions.h fonction.c, ajoutez les fonctions réalisées dans les exercices précédents.

  2. Réaliser le programme principal dans le fichier “tp4.c”

#include <stdlib.h>
#include <stdio.h>
#include "fonction.h"

int main(){
    printf("Programme principal TP4 \n");
    return 0;
}
  1. Le programme principal doit avoir le fonctionnement suivant :