Trouver le plus grand diviseur commun en utilisant la récursivité

Introduction

En mathématiques, le plus grand commun diviseur (PGCD) de deux nombres est généralement défini comme le plus grand entier positif qui divise les deux nombres sans laisser de reste. Dans ce laboratoire, nous allons apprendre à écrire un programme C pour trouver le PGCD de deux nombres en utilisant la récursion.

Note : Vous devez créer le fichier ~/project/main.c vous-même pour pratiquer la programmation et apprendre à le compiler et à l'exécuter avec gcc.

cd ~/project
## créer main.c
touch main.c
## compiler main.c
gcc main.c -o main
## exécuter main
./main

Lecture des nombres d'entrée

Tout d'abord, nous devons prendre deux nombres d'entrée entiers saisis par l'utilisateur pour trouver leur PGCD. Nous utiliserons la fonction scanf() pour lire l'entrée.

#include<stdio.h>

int main()
{
    int a, b;
    printf("Entrez deux nombres pour trouver le PGCD : \n");
    scanf("%d%d", &a, &b);
    // reste du code
    return 0;
}

Définition de la fonction récursive pour trouver le PGCD

Nous utiliserons une fonction récursive pour trouver le PGCD des deux nombres d'entrée. La fonction récursive aura deux paramètres entiers. La fonction continuera à s'appeler elle-même jusqu'à ce que les deux nombres aient la même valeur et retournera cette valeur comme PGCD.

int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

Appel de la fonction récursive depuis la fonction principale

Dans cette étape, la fonction récursive sera appelée avec les deux nombres d'entrée (a et b). La valeur de retour de la fonction récursive sera stockée dans une variable entière (gcd).

int gcd = find_gcd(a, b);
printf("PGCD de %d et %d est : %d\n", a, b, gcd);

Exemple de code complet

#include <stdio.h>

// déclaration de la fonction récursive
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("Entrez deux nombres pour trouver le PGCD : \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("PGCD de %d et %d est : %d\n", a, b, gcd);
    return 0;
}

// définition de la fonction
int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

Résumé

Dans ce laboratoire, nous avons appris à écrire un programme C pour trouver le PGCD de deux nombres en utilisant la récursivité. Nous avons utilisé une fonction récursive pour calculer le PGCD en faisant appel à la fonction elle-même avec des paramètres d'entrée modifiés jusqu'à ce qu'elle atteigne un cas de base. Ce programme peut être utilisé pour résoudre des problèmes mathématiques qui nécessitent le calcul du PGCD de deux nombres.