Récursivité en C - Applications résolues


1) Calculez n! dans la version iterative.
#include<stdio.h>
long int factoriel (int n)
{
	long int f=1;
	for (int i=1; i<=n;i++)
	f=f*i;
	return f;
}
void main()
{
	int n;
	printf("Introduire n= ");
	scanf("%d", &n);
	
	if(!n)
		printf("0!=1\n");
	else
		printf("%d!=%ld\n",n,factoriel(n));
 
  getchar();
  int var;
  scanf("%d", var);
}

2) Calculer n! dans la version recursive.
// factoriel(3)=3*factoriel(2)=3*2*factoriel(1)=3*2*1

#include<stdio.h>
long int factoriel (int n)
{
	if (n==1) return 1;
	else return n*factoriel(n-1);
}
void main()
{
	int n;
	printf("Introduire n= ");
	scanf("%d", &n);
	
	if(!n)
		printf("0!=1\n");
	else
		printf("%d!=%ld\n",n,factoriel(n));
 
 	getchar();
  	int var;
  	scanf("%d", var);
}

3) Calculer recursivement la somme des elements d’une chaine.
#include<stdio.h>
int somme(int n)
{ 
	if (n==0) return 0;
	else return (n + somme(n-1));
}
void main()
{
	int n;				
	printf("Introduire n: ");
	scanf("%d", &n);
	printf("La somme des elements est %d\n",somme(n));
 
  	getchar();
  	int var;
  	scanf("%d", var);
}

4) Ecriver une fonction propre qui realise le calcule recursive de la somme des elements d’un vecteur, de n<=10, de nombre reel. Ecriver la fonction main qui lit les dates du clavier, calcule la somme, en utilisant la fonction recursive anterieurement definie et affiche la valeur obtenue.
#include <stdio.h>
#include <conio.h>

int a[10], n;
int somme (int n, int a[10])
{
	if(n==0) return 0;
	else return(a[n]+somme(n-1,a));
}
void main()
{ 
	// Lire les dates d’entree
	printf("Introduire le nombre des elements: ");
	scanf("%d", &n);
	for (int i=1; i<=n; i++)
	{
		printf("element [%d] = ", i);
		scanf("%d", &a[i]);
	} 
	// Affichage des resultats
	printf("somme = %d", somme(n,a));
 
	getch();
}

5) Ecrire un programme C, pour rezoudre le cmmdc entre deux nombres entiers sans signe (pour determiner le cmmdc-ului on va utiliser l’algrithme de Euclid par diminutions). Version iterative.
#include <stdio.h>
#include <conio.h>

unsigned int cmmdc(unsigned int a, unsigned int b)
{
	while(a!=b)
	{
		if(a>b)
			a=a-b;
		else
			b=b-a;
	}
	return a;
}
void main()
{
	unsigned int x,y;
	printf("Introduire x: ");
	scanf("%u",&x);
	printf("Introduire y: ");
	scanf("%u",&y);
 
	if(!x || !y)		//si x=0 or y=0
	printf("cmmdc(%u,%u) = 1\n",x,y);
	else
	printf("cmmdc(%u,%u) = %u\n",x,y,cmmdc(x,y));
 
	getch();
}

6) Ecrire un programme C, pour rezoudre le cmmdc entre deux nombres entiers sans signe (pour determiner le cmmdc on va utiliser l’algorithme de Euclid par diminutions). Version recursive.
#include <stdio.h>
#include <conio.h>

unsigned int cmmdc(unsigned int a, unsigned int b)
{
	if(a==b) return a;
	else
		if(a>b) return cmmdc(a-b,b);
		else return cmmdc(a,b-a);
}
void main()
{
	unsigned int x,y;
	printf("Introduire x: ");
	scanf("%u",&x);
	printf("Introduire y: ");
	scanf("%u",&y);
 
	if(!x || !y)		//si x=0 or y=0
	printf("cmmdc(%u,%u) = 1\n",x,y);
	else
	printf("cmmdc(%u,%u) = %u\n",x,y,cmmdc(x,y));
 
	getch();
}

7) Ecrire un programme C, pour rezoudre le cmmdc de n nombres entiers sans signe (pour determiner le cmmdc on va utiliser l’algorithme de Euclid par diminutions). Version recursive.
#include <stdio.h>
#include <conio.h>

unsigned int cmmdc_2(unsigned int a, unsigned int b)
{
	if(a==b) return a;
	if(a>b) return cmmdc_2(a-b,b);
	else
	return cmmdc_2(a,b-a);
}
unsigned int cmmdc_n(unsigned int x[], int n)
{
	if (n==2) return cmmdc_2(x[0],x[1]);
	else	return cmmdc_2(cmmdc_n(x,n-1),x[n-1]);
}
void main()
{
	unsigned int x[20];
	int n;
	printf("Introduire n: "); 
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		printf("element %d= ",i+1);
		scanf("%u",&x[i]);
	}
	if (n==1)
	printf("\nCmmdc des nombres: %u",x[0]);
	else
	printf("\nCmmdc des nombres: %u",cmmdc_n(x,n));
 
	getch();
}

8) On considere les suivantes declarations et conventions:
typedef int vector[20];
x – est un vecteur (chaine des elements)
n – est sa longueur (n>=1)
In faudra ecrire des fonctions recursives pour determiner, pour un vecteur x de longueur n, les suivantes:
a. lecture des components de la chaine
b. affichage des elements d’une chaine
c. somme ds components
d. produit des components
e. nombre des components negatifs
f. produit des components positifs
g. moyen aritmetique des elements
#include<stdio.h>
#include<conio.h>
/* type propre defini pour memoriser des chaines des elements entiers, avec une
Dimension maximum de 20 de components */
typedef int vecteur[20];
//fonction de lire
void lire(vecteur x,int n) //n est la dimension reelle de la chaine
{
	//lire le dernier element de la chaine
	printf("\telement %d: ",n);
	scanf("%d",&x[n-1]);
	if(n>=2)
	lire(x,n-1); //l’appel recursive de la fonction
}
//fonction d’affichage
void affichage(vecteur x,int n) //n est la dimension reelle (nombre d’elements de la chaine)
{
	//afficher le dernier element
	printf("%d ",x[n-1]);
	if(n>=2)
	affichage(x,n-1); //appell recursive de la fonction
}
//addition des components d’une chaine
int somme(vecteur x,int n) //n on condidere indice l’lement de la chaine
{
if(n==-1) return 0; /*la situation quand il n’y a pas d’elements dans la chaine, 
				pozition n=-1  n’est pas dans la chaine*/
	else return x[n]+somme(x,n-1);
}
//produit des components
int produit(vecteur x,int n)
{
	if(n==-1) return 1;
	else return x[n]*produit(x,n-1);
}
//nombre des components negatifs
int nombre_negatif(vecteur x,int n)
{
	//il faut se positioner sur le premier element de la chaine et verifier si’il est negatif
if(n==0) return (x[n]<0); //l’expression reconditionee va retourner 1 en cas de vrai et 0 in caz de faux
	else return (x[n]<0)+nombre_negatif(x,n-1);
}
//produit des components positifes
int produit_positife(vecteur x,int n)
{
	if(n==0) return (x[n]>0?x[n]:1); /* on utilise l’opperateur de conditioner,
	qui, si l’expression evaluee comme vraie on va prendre en calcule x[n], autrement, la valeur 1 */
	else return (x[n]>0?x[n]:1)*produit_positife(x,n-1);
}
//moyen aritmetique des components de la chaine
float media(vecteur x, int m, int n) /*on notte avec m l’ indice des elementsr, 
					et avec n la dimension reelle de la chaine*/
{
	return (float)x[m]/n + ((m!=0)?media(x,m-1,n):0);
	/* - am folosit expresia (float) pour une conversion explicite du resultat
	Vers un type reel
	- par x[m]/n on comprend un element (premierement, il sera le dernier de la chaine) 
	divise au nombre des components */
}
//fonction principale dans l’execution
void main()
{
	vecteur x; //chaine des elements
	int n; //sa dimension (nombrte des components lus)
 
	//realiser l’opperation de lire de la chaine
	printf("Entrer le nombre des elements: ");
	scanf("%d",&n);
	printf("Introduire les elements de la chaine:\n");
	lire(x,n);
 
	//realization de l’opperation de’affichage de la chaine
	printf("La chaine des elements est: ");
	affichage(x,n);
 
	//la somme des elements
	printf("\nLa somme des elements: %d",somme(x,n-1)); /* on appel avec n-1, 
	car on a dit que ce parametre represent l’indice du dernier element de la chaine */
	//le produit des elements
	printf("\nLe produit des elements: %d",produit(x,n-1));
	//nombre des elements negatifs de la chaine
	printf("\nNombre des elements negatifs: %d",nombre_negatif(x,n-1));
	//produit des components positifs
	printf("\nproduit des elements positifs: %d",produit_positife(x,n-1));
	//media componentelor din sir
	printf("\nMoyen des components de la chaine: %.2f",media(x,n-1,n)); /* premier parametre - chaine,
		deuxieme parametre – l’indice du dernier element de la chaine, 
		le troixieme parametre – dimension reelle de la chaine (nombre ds elements lus) */ 
	getch();
}

9) Ecrire une fonction recursive pour determiner la somme des ciffres d’un nombre naturel. A savoir: On doit isoler la derniere ciffre, et pour n on attribue le reste de division entre la vieille valeur et 10.
#include<stdio.h>
#include<conio.h>

int somme(int n)
{
	if(!n) return 0;		//!n=s’il n’y a pas de n
	else return n%10+somme(n/10);
} 
void main()
{
	int n;
	printf("Introduire le nombre: ");
	scanf("%d", &n);
 
	printf("La somme des ciffres du nombre est: %d", somme(n));
 
	getch();
}

10) Ecrire une fonction recursive pour transformer un nombre naturel n, de base 10 en base k (1<k<=10). A savoir: On divise le nombre par k, on retient le reste, on le divise par k,... jusqu’a ce que le reste sera mois que le diviseur. On obtint le resultat en ecrivant en ordre enverse la chaine des restes obtenus. On liste le reste apres l’autoapel.
#include<stdio.h>
#include<conio.h>

void transform(int n,int b)
{
	int rest=n%b;
	if (n>=b) transform(n/b,b);
	printf("%d",rest);
}
void main()
{
	int n,b;
	printf("n="); scanf("%d",&n);
	printf("base="); scanf("%d",&b);
	transform(n,b);
 	getch();
}

11) Lire x de Z . On demande un sous-programme pour calculer la fonction Manna-Pnuelli:
	x-1, x>=12
F(x)=
	F(F(x+2)), x<12
#include<stdio.h>
#include<conio.h>

int F(int x)
{
	if (x>=12) return x-1;
	return F(F(x+2));
}
void main()
{
	int x;
	printf("x="); scanf("%d",&x);
	printf("La valeur de la fonction est: %d",F(x));
 
	getch();
}

12) On considere la chaine de Fibonacci comme ca:
	0, n=0
Un=    	1, n=1
	Un-1+Un-2, autre
On lit n, un nombre naturel. Calculez Un, version iterative.
#include<stdio.h>
#include<conio.h>

void main()
{
	int n,U0=0,U1=1,U2;
	printf("n="); scanf("%d",&n);
	if(!n) printf("%d",U0);
	else
		if (n==1) printf("%d",U1);
		else
		{
			for (int i=2;i<=n;i++)
			{
				U2=U0+U1;
				U0=U1;
				U1=U2;
			}
			printf("%d",U2);
		}
/*
ptr. n=3
i=2: U2=U0+U1
U0=U1
U1=U2
i=3: U2=U1+U2
*/
	getch();
}

13) On considere la chaine Fibonacci comme:
	0, n=0
Un=    	1, n=1
	Un-1+Un-2, altfel
On lit n, un nombre naturel. Calculez Un, version iterative.
#include<stdio.h>
#include<conio.h>

int U (int n)
{
	if (!n) return 0;
	else	if (n==1) return 1;
	else	return U(n-1)+U(n-2);
}
 
void main()
{
	int n;
	printf("Introduire n=");	
	scanf("%d",&n);
 
	printf("La valeur de la chaine en n est: %d",U(n));
 
	getch();
}
Cookies help us deliver our services. By using our services, you agree to our use of cookies.