[PDF] Introduction `a la Programmation des Algorithmes 3.2. Langage C

View - Download Introduction `a la Programmation des Algorithmes 3.2. Langage C

Previous PDF

Next PDF

Introduction `a la Programmation des Algorithmes

3.2. Langage C - Fonctions r´ecursives

Fran¸cois Fleuret

https://fleuret.org/11x001/On peut d´eifinir des fonctions math´ematiques de mani`ere r´ecursive.

Par exemple la fonction factorielle:

f(n) =( 1 si n<= 0, n·f(n-1)sinon.

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 1 / 21

Des constructions similaires sont possibles en programmation.

1#include

2

3intfactorielle (intn) {

4if(n<= 0 )return 1 ;

5elsereturn n * fa ctorielle(n- 1 );

6} 7

8intmain (void){

9for(intk = 0 ;k <= 5 ;k ++){

10printf("%d! = %d\n",k, factorielle(k));

11}

12return0 ;

13} aiÌifiÌiche

0! = 1

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 2 / 21Cela nous donne par substitution,

factorielle( 4 4 factorielle( 3 4 3 factoriell e( 2 4 3 2 factorielle( 1 4 3 2 1 factor ielle( 0 4 3 2 1 1 12 2 1 1 24
1 1 24
1 24

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 3 / 21

Une fonction r´ecursive doit int´egrer unecondition d'arrˆetqui retourne une valeur sans appel r´ecursif.

1intfactorielle (intn) {

2if(n<= 0 )return 1 ;

3elsereturn n * fa ctorielle(n- 1 );

4}Sans une telle condition, ou si elle n'est jamais r´ealis´ee, la fonction ne s'arrˆete

pas. Par exemple si nous ´ecrivons une fonction pour calculerPn k=1k:

1intsomme (intn) {

2if(n== 1 )return 1 ;

3elsereturn n + so mme(n- 1 );

4}Elle ne s'arrˆete pas si elle est appel´ee avecn<=0.Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 4 / 21Une bonne habitude de programmation est de v´eriifier que les valeurs des

arguments ont bien les propri´et´es attendues et `a r´eagir en cons´equence si ce n'est pas le cas. Une mesure brutale consiste `a appelerabort, d´eifinie dans stdlib.h, qui crash le programme.

1#include

2#include

3

4intsomme (intn) {

5if(n<= 0 )abort();

6if(n== 1 )return 1 ;

7elsereturn n + so mme(n- 1 );

8} 9

10intmain (void){

11printf("%d\n",somme (10));

12printf("%d\n",somme (-3));

13return0 ;

14} aiÌifiÌiche 55

Aborted (core dumped)

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 5 / 21

Il arrive que l'on veuille programmer plusieurs fonctions qui s'utilisent mutuellement. On parle alors der´ecursion mutuelle. On doit alors d´eclarer l'une d'elle avant de les d´eifinir.

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 6 / 211#include

2#include

3

4intimpair (intn);

5

6intpair (intn) {

7if(n< 0 )a bort();

8elseif (n== 0 )re turn1 ;

9elsereturn impair(n -1);

10} 11

12intimpair (intn) {

13if(n< 0 )a bort();

14elseif (n== 0 )re turn0 ;

15elsereturn pair(n -1);

16} 17

18intmain (void){

19printf("%d %d %d\n",pair( 13),pair( 4),impair( 6));

20return0 ;

21}

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 7 / 21

Une convention importante en C pour l'´evaluation d'op´erateurs bool´eens est que les op´erandes ne sont elles-mˆemes calcul´ees que si cela est n´ecessaire. On parle d'´evaluationparesseuse.

Par exemple pour ´evaluer

0 f(x) comme l'´evaluation se fait de gauche `a droite, il n'est pas n´ecessaire de calculer f(x).Si nous d´eifinissons

1intdivise (inta, int b) {

2printf("Est-ce que %d divise %d?\n",b, a);

3returna %b== 0 ;

4}Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 8 / 215intmain (void){

6printf("calcul de q\n");

7intq = div ise(10,5 )&& divise( 20,4 );

8printf("calcul de r\n");

9intr = div ise(10,3 )&& divise( 20,4 );

10printf("calcul de t\n");

11intt = div ise(10,3 )|| divise( 20,4 );

12printf("calcul de u\n");

13intu = div ise(10,2 )&& divise( 20,4 )&& divise( 6,4 )&& divise( 15,3 );

14return0 ;

15} aiÌifiÌiche calcul de q

Est-ce que 5 divise 10?

Est-ce que 4 divise 20?

calcul de r

Est-ce que 3 divise 10?

calcul de t

Est-ce que 3 divise 10?

Est-ce que 4 divise 20?

calcul de u

Est-ce que 2 divise 10?

Est-ce que 4 divise 20?

Est-ce que 4 divise 6?

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 9 / 21

Cela nous permet par exemple de re-´ecrire

1intpair (intn) {

2if(n< 0 )a bort();

3returnn == 0 || impair(n -1);

4} 5

6intimpair (intn) {

7if(n< 0 )a bort();

8returnn > 0 && pair(n -1);

9}

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 10 / 21Notez que ces fonctions ´etaient des exemples r´ecursifs tr`es ineiÌifiÌicaces. En

pratique on ´ecrirait:

1intpair (intn) {

2if(n< 0 )a bort();

3returnn %2== 0 ;

4} 5

6intimpair (intn) {

7if(n< 0 )a bort();

8returnn %2== 1 ;

9}

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 11 / 21

R´ecursivit´e terminale

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 12 / 21Nous avons vu que les variables locales sont r´eserv´ees sur une "pile" en

m´emoire. Ce m´ecanisme est le mˆeme pour les variables locales `a une fonction.En plus des variables, quand une fonction est appel´ee, l'ordinateur m´emorise sur

cette pile des informations n´ecessaires pour savoir o`u continuer l'ex´ecution quand la fonction se termine. Cela signiifie qu'en pratique un programme occupe pour cela une quantit´e de m´emoire proportionnelle au nombre d'appels de fonctions imbriqu´es.

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 13 / 21

Cela peut poser probl`eme si on fait beaucoup d'appels r´ecursifs

1#include

2

3/* retourne le nombre de diviseurs de n qui sont >= k */

4intnb_diviseurs (intn, int k) {

5if(k> n) r eturn0 ;

6intnb = nb _diviseurs(n,k + 1 );

7if(n% k == 0 )nb ++;

8returnnb;

9} 10

11intmain (void){

12printf("%d\n",nb_di viseurs(245,1 ));

13printf("%d\n",nb_di viseurs(317322,1 ));

14printf("%d\n",nb_di viseurs(8133453,1 ));

15return0 ;

16} aiÌifiÌiche 6 36

Segmentation fault (core dumped)

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 14 / 21Ce probl`eme peut ˆetre ´evit´e dans une fonctionsi aucune op´eration n'est

n´ecessaire entre le retour de l'appel r´ecursif et le retour de la fonction elle mˆeme.

Puisque l'ordinateur n'a pas besoin de repasser par la fonction apr`es l'appel, ilpeut revenir directement apr`es le premier appel `a cette fonction r´ecursive, et ne

conserve rien sur la pile apr`es chaque appel r´ecursif. On parle alors de fonctionr´ecursive terminale.

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 15 / 21

Voici une version r´ecursive terminale:

1#include

2

3/* est-ce que n a un diviseur >= k ? */

4inta_un_diviseur (intn, int k) {

5if(k> n) r eturn0 ;

6if(n%k== 0 )return 1 ;

7returna_un_diviseur (n,k +1);

8} 9

10intmain (void){

11printf("%d\n",a_un_ diviseur(479001599,2 ));

12return0 ;

13} aiÌifiÌiche 0 La fonctiona_un_diviseurappel´ee ligne 11 entraˆınera un grand nombre d'appels r´ecursifs, mais d`es que l'un des returns des lignes 5 ou 6 sera ex´ecut´e, le programme pourra retourner directement `a la ligne 11, sans repasser un grand nombre de fois ligne 7.

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 16 / 21R´ecursion

R´ecursion terminale

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 17 / 21

Il est g´en´eralement possible de re-´ecrire une fonction r´ecursive non-terminalesous une forme r´ecursive terminale en rajoutant des arguments qui repr´esentent

des quantit´es accumul´ees. Cette fonction n'´etait pas r´ecursive terminale, d'o`u le crash quand elle a ´et´e appel´ee avec une grosse valeur:

1intnb_diviseurs (intn, int k) {

2if(k> n) r eturn0 ;

3intnb = nb _diviseurs(n,k + 1 );

4/* ici nb est le nombres de diviseurs de n qui sont >= k+1 */

5if(n% k == 0 )nb ++;

6/* ici nb est le nombres de diviseurs de n qui sont >= k */

7returnnb;

8}

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 18 / 21Par exemple:

1#include

2

3/* retourne nb + le nombre de diviseurs de n qui sont >= k de fa¸con `a

4ce que si on l'appelle avec nb = le nombre de diviseurs de n qui sont

5< k elle retourne le nombre total de diviseurs de n */

6

7intnb_diviseurs (intn, int k, int nb) {

8if(k> n) r eturnn b;

9/* ici nb est le nombre de diviseurs de n qui sont < k */

10if(n% k == 0 )nb ++;

11/* ici nb est le nombre de diviseurs de n qui sont <= k */

12returnnb_diviseurs( n,k + 1 ,nb);

13} 14

15intmain (void){

16printf("%d\n",nb_di viseurs(245,1 ,0 ));

17printf("%d\n",nb_di viseurs(317322,1 ,0 ));

18printf("%d\n",nb_di viseurs(8133453,1 ,0 ));

19return0 ;

20} aiÌifiÌiche 6 36
16

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 19 / 21

On peut cacher les arguments suppl´ementaires en cr´eant une fonction qui ex´ecute le premier appel r´ecursif:

1/* retourne nb + le nombre de diviseurs de n qui sont >= k */

2intnb_diviseurs_re c(intn ,int k, int nb) {

3if(k> n) r eturnn b;

4if(n% k == 0 )nb ++;

5returnnb_diviseurs_ rec(n,k + 1 ,nb);

6} 7

8intnb_diviseurs (intn) {

9returnnb_diviseurs_ rec(n,1 ,0 );

10}

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 20 / 211#include

2#include

3

4floatracine_rec (floatx, float a, float b, float eps) {

5floatc = ( a+ b) / 2 ;

6if(b- a < eps) return c;

7else

8if(c* c >= x)

9returnracine_rec(x, a, c, eps);

10else

11returnracine_rec(x, c, b, eps);

12} 13

14floatracine (floatx) {

15if(x< 0 )a bort();

16returnracine_rec(x, 0 ,x +1,1e-6 );

17} 18

19intmain (void){

20printf("%f\n",racine (2));

21return0 ;

22}
aiÌifiÌiche

1.414213

Fran¸cois Fleuret Introduction `a la Programmation des Algorithmes / 3.2. Langage C - Fonctions r´ecursives 21 / 21

quotesdbs_dbs45.pdfusesText_45

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal

[PDF] hsa prof

[PDF] indemnite tuteur stagiaire education nationale