Programme de baccalauréat en informatique Algorithmique et programmation IFT-17582 Abder Alikacem Abder Alikacem Semaine 13 La récursivité Département

Programme de baccalauréat en informatique Algorithmique et programmation

IFT-17582

Abder AlikacemAbder Alikacem

Semaine 13La récursivité

Département d’informatique et de génie logiciel

Édition septembre 2007

Plan

• Définition récursive d’un problème• Technique: diviser pour régner• Récursion, conditions d’arrêt et convergence• Efficacité et inefficacité des algorithmes récursifs• Exemples

Lecture: chapitre 13 des notes de cours

La récursivité est l'art de définir une fonction en termes d'elle-même.

Pourquoi la récursivité?

Pour faire souffrir les étudiantsParce que les profs adorent faire souffrir les étudiants

La récursivité

La récursivité : Plusieurs problèmes sont résolus de façonrécursive parce que :

• naturellement décrits de façon récursive (en mathématiques entre autres : factorielle, Fibonacci, PGCD, etc.)

• ça simplifie la résolution du problème (diviser pour régner : ré-appliquer un même traitement sur un échantillon de données d’une taille de plus en plus petite)

En informatique, la programmation avancée utilise souvent des techniques de programmation récursive.

La récursivité

Soit f, une fonction comprenant un appel à elle-même, soit directement, soit indirectement. Alors, f est une fonction récursive.

Définition

La récursivité

Le langage C autorise la récursivité des appels de fonctions. Celle-ci peut prendre la forme d’une :

récursivité directe : une fonction comporte, dans sa définition, au moins un appel à elle-même.

int f1 ( . . . ){ x = f1 ( . . . );}

La récursivité

récursivité indirecte (croisée) : l'appel d'une fonction entraîne une séquence d’appels de fonctions qui inclueraéventuellement la fonction de départ

int f1 ( . . . ){ x = f2 ( . . . );}

int f2 ( . . . ){ y = f1 ( . . . );}

La récursivité

Une fonction récursive doit posséder les deux propriétés suivantes:

il doit exister certains critères, appelés critères d'arrêt ou conditions d'arrêt, pour lesquels la fonction ne s’appelle pas elle-même;

chaque fois que la procédure s’appelle elle-même (directement ou indirectement), elle doit converger vers ses conditions d'arrêt.

Une fonction récursive possédant ces deux propriétés est dite bien définie.

La récursivité

Récursivité : Diviser pour régner

• Expression récursive du problème :• L’ « équation » de la récursivité.

• Condition d’arrêt :• Quand est-ce qu’on arrête les appels récursifs?

• Convergence (vers la condition d’arrêt):• Une petite « preuve » et les conditions qui nous assure

qu’on atteindra la condition d’arrêt.

Idée : Diviser pour régner• expression récursive du problème (récursion)

n! = n x (n-1) x (n-2) x (n-3) x … x 1 = n x (n-1)!

• conditions d’arrêt1! ou 0!

• convergence vers une des conditions d’arrêt

si n = 0 ou n = 1 alors on a les conditions d’arrêt si n 2 alors la soustraction par 1 nous amènera vers n = 1(n n-1 n-2 n-3 … 2 1)

donc convergence si n 0

La récursivité


Structure générale d’une fonction récursive

{if(/* !!condition de convergence */)

exit(1);

if(/*condition d’arrêt*/)return(/*Ce qu’elle doit retourné*/);

elseappel récursif

}Traitemen

t

Calculer la factorielle d’un nombre entier n

• récursion:

n! = n x (n-1) x (n-2) x (n-3) x … x 1 = n x (n-1)!

• conditions d’arrêt

1! ou 0!

• convergence vers une des conditions d’arrêt

si n 0

Exemple1

long fact(int n){

if (n < 0) exit(1); /* hypothèse de convergence : n 0 */

if (n == 0 || n == 1) return 1; /* conditions d’arrêt */

else return n * fact(n - 1); /* appel récursif */}

Calculer la factorielle d’un nombre entier n

Suite de Fibonacci

• Léonardo Pisano dit le « fils de Bonacci »• Entre autre : L’équation de la reproduction

des lapins

• 1, 2, 3, 5, 8, 13, 21, 34, …

Exemple2

La suite de Fibonacci

fn = fn-1 + fn-2 récursion

f1 = 1 conditions d’arrêtf2 = 2

convergence ?

Exemples :

f3 = f2 + f1 = 3f4 = f3 + f2 = 5

Exemple2

long fibo(int n){

if (n < 1) exit(1);/* assertion : n >= 1 */

if (n == 1) return 1; /* cond. d’arrêt #1 */if (n == 2) return 2; /* cond. d’arrêt #2 */else /* appels récursifs */ return fibo(n - 1) + fibo(n - 2);

}

La suite de Fibonacci

Exemple3

La légende des Tours de Hanoï remonte aux origines des temps ...

Pour un certain nombre de disques, le problème est soluble si nous sommes capables d’accomplir les actions suivantes:

1.Déplacer les n-1 disques du dessus de Src vers Aux (utilisant Dest comme tour auxilaire)

2.Déplacer le disque restant de Src vers Dst 3.Déplacer les n-1 disques de Aux vers Dst

(utilisant Src comme tour auxiliaire)

void hanoi(int nbDisques, char Src,char Aux, char Dest){ if (nbDisques == 1) /*condition d’arret*/ { printf("%c -> %c\n", Src, Dest); }

else { /*premier appel recursif*/ hanoi( (nbDisques-1) , Src, Dest, Aux);

printf("%c -> %c\n", Src, Dest);

/*deuxieme appel recursif*/ hanoi( (nbDisques-1) , Aux, Src, Dest); }}

Un palindrome est un mot qui peut être lu de la même manière de gauche à droite ou de droite à gauche.

Exemples :LavalcolocàAbbaelle...

Les palindromes

Exemple4

1. La récursion :

Les palindromes

1. La récursion : <ch, l> est un palindrome si :

ch[0] == ch[l-1] et <ch+1, l-2> est un palindrome.

2. Les conditions d'arrêt :

Les palindromes



2. Les conditions d'arrêt : 1er cas : un seul caractère (l = 1) VRAI

Les palindromes



2. Les conditions d'arrêt : 1er cas : un seul caractère (l = 1) VRAI 2e cas : une chaîne vide (l = 0) VRAI

Les palindromes

1. La récursion :<ch, l> est un palindrome si :


2. Les conditions d'arrêt : 1er cas : un seul caractère (l = 1) VRAI 2e cas : une chaîne vide (l = 0) VRAI 3e cas : si ch[0] != ch[l-1] FAUX (supposant que l 0)

3. La convergence :

Les palindromes

1. La récursion :<ch, l> est un palindrome si :


2. Les conditions d'arrêt : 1er cas : un seul caractère (l = 1) VRAI 2e cas : une chaîne vide (l = 0) VRAI 3e cas : si ch[0] != ch[l-1] FAUX (supposant que l 0)

3. La convergence :comme l est nécessairement 0, sa valeur se rapproche d'une condition d'arrêt à chaque appel récursif

Les palindromes

typedef enum {FAUX, VRAI} Bool;

Bool palindrome(char * mot, int longueur)

{

}

Les palindromes



{if (longueur < 0) exit(1);

/* assertion : longueur >= 0 */

}

Les palindromes





/* 2 conditions d’arrêt */

if ((longueur == 0) || (longueur == 1)) return(VRAI);

}

Les palindromes







/* 3e condition d’arrêt */if (mot[0] != mot[longueur-1]) return(FAUX);else

}

Les palindromes







/* 3e condition d’arrêt */if (mot[0] != mot[longueur-1]) return(FAUX);else /* appel récursif */ return palindrome(mot+1, longueur-2);

}

Les palindromes

s = x0 + x1 + ... + xn-1

1. La récursion :

La somme des éléments d’un tableau

Exemple5

s = x0 + x1 + ... + xn-1

1. La récursion : s(x0, ... , xn-1) = x0 + s(x1, ... , xn-1)

2. La condition d'arrêt :


s = x0 + x1 + ... + xn-1


2. La condition d'arrêt : s(x0) = x0 (1 seul terme)

3. La convergence :


s = x0 + x1 + ... + xn-1


2. La condition d'arrêt : s(x0) = x0 (1 seul terme)

3. La convergence : n > 0 et décroît vers 1


long somme(int tab[ ], int n, int debut){

}


long somme(int tab[ ], int n, int debut){ if (n < 1) exit(1); /* assertion : n >= 1 */

}


long somme(int tab[ ], int n, int debut){ if (n < 1) exit(1); /* assertion : n >= 1 */

/* assertion : debut est un indice valide, debut 0 */

}


long somme(int tab[ ], int n, int debut){ if ((n < 1) || (debut < 0)) exit(1); /* assertion : n >= 1 */


}




/* condition d’arrêt */

}




/* condition d’arrêt */ if (n == 1) return tab[debut]; else

}


long somme(int tab[ ], int n, int debut){ if ((n < 1) || (debut < 0)) exit(1); /* assertion : n >= 1 */ /* assertion : debut est un indice valide, debut 0 */

/* condition d’arrêt */ if (n == 1) return tab[debut]; else /* appel récursif */

return tab[debut] + somme(tab, n-1, debut+1);}


Somme d’un tableau: autre version

Somme(tab[], n) = tab[0] + Somme(tab + 1, n-1)

long somme(int * tab, int n){

if (n < 1)/* hypothèse de convergence : n 1*/exit(1);

if (n == 1) /* condition d’arrêt */return tab[0];

else /* appel récursif */return tab[0] + somme(tab + 1, n – 1);

}

Soit ch1 et ch2, les deux chaînes à comparer.

1. La récursion :

La comparaison de 2 chaînes de caractères

Exemple6


1. La récursion : ch1 est égale à ch2 à partir de debut si : ch1[debut] == ch2[debut] et ch1 et ch2 sont égales à partir de debut+1.





2. Les conditions d'arrêt : ch1[debut] != ch2[debut] FAUX





ch1[debut] == '\0‘si ch1[debut] == ch2[debut] VRAI

si ch1[debut] != ch2[debut] FAUX

3. La convergence :





ch1[debut] == '\0‘si ch1[debut] == ch2[debut] VRAI

si ch1[debut] != ch2[debut] FAUX

3. La convergence :Balayage des 2 chaînes jusqu'à la fin de chaîne.


Bool egal(char *ch1, char *ch2, int debut){

}


Bool egal(char *ch1, char *ch2, int debut){ /* assertion : ch1 pointe sur une chaîne de caractères */

}


Bool egal(char *ch1, char *ch2, int debut){ /* assertion : ch1 pointe sur une chaîne de caractères */ /* assertion : debut est un indice valide, debut 0 */

}


Bool egal(char *ch1, char *ch2, int debut){ /* assertion : ch1 pointe sur une chaîne de caractères */ /* assertion : debut est un indice valide, debut 0 */ /* assertion : debut strlen(ch1) */

}


Bool egal(char *ch1, char *ch2, int debut){ /* assertion : ch1 pointe sur une chaîne de caractères */ /* assertion : debut est un indice valide, debut 0 */ /* assertion : debut strlen(ch1) */ if ((debut < 0) || (debut > strlen(ch1))) exit(1);

}



/* condition d’arrêt : sur la fin de chaîne de ch1 */

}



/* condition d’arrêt : sur la fin de chaîne de ch1 */ if (ch1[debut] == '\0')

if (ch2[debut] == '\0') return(VRAI);else return(FAUX);

else

}




if (ch2[debut] == '\0') return(VRAI);else return(FAUX);

else /* condition d’arrêt : inégalité des car. correspondants */

}




if (ch2[debut] == '\0') return (VRAI);else return (FAUX);

else /* condition d’arrêt : inégalité des car. correspondants */if (ch1[debut] != ch2[debut]) return(FAUX);else

}




if (ch2[debut] == '\0') return(VRAI);else return (FAUX);

else /* condition d’arrêt : inégalité des car. correspondants */if (ch1[debut] != ch2[debut]) return(FAUX);else /* appel récursif */ return egal(ch1, ch2, debut+1);

}


Comparaison de chaînes: autre version

Egal(mot1, mot2) = *mot1 = *mot2 ET Egale(mot1 + 1,mot2 + 1)

Bool egal(char * mot1, char * mot2){

if (*mot1 != *mot2) /* condition d’arrêt */return FAUX;

if (*mot1 == ‘\0’) /* condition d’arrêt */if (*mot2 == '\0') return VRAI;

else return FAUX ;else /* appel récursif */

return egal(mot1 + 1, mot2 + 1);}

1. La récursion :

Vérifier qu’une suite de nombres est triée

<x0, x1, …, xn-1>

ExempleExemple77

1. La récursion : <x0, x1, …, xn-1> est triée si :

x0 x1 et

<x1, …, xn-1> est triée.



<x0, x1, …, xn-1>


x0 x1 et


2. Les conditions d'arrêt : <x0> est triée (longueur = 1 VRAI)


<x0, x1, …, xn-1>


x0 x1 et



x0 > x1 FAUX

3. La convergence :


<x0, x1, …, xn-1>


x0 x1 et



x0 > x1 FAUX

3. La convergence :La taille de la séquence regardée diminuejusqu’à 1.


<x0, x1, …, xn-1>

Bool triee(int x[ ], int debut, int longueur){

}


<x0, x1, …, xn-1>


/* assertion : longueur 1 *//* assertion : debut est un indice valide, debut 0 */

if ((longueur < 1) || (debut < 0)) exit(1);

}


<x0, x1, …, xn-1>




/* cond. d’arrêt : longueur = 1 */if (longueur == 1) return VRAI;else /* cond. d’arrêt : bris de l ’ordre */

}


<x0, x1, …, xn-1>





if (x[debut] > x[debut+1]) return FAUX;else

}


<x0, x1, …, xn-1>





if (x[debut] > x[debut+1]) return FAUX;else /* appel récursif */

}


<x0, x1, …, xn-1>





if (x[debut] > x[debut+1]) return FAUX;else /* appel récursif */ return triee(x, debut+1, longueur-1);

}


<x0, x1, …, xn-1>

Tableau trié : autre version

trie(tab[], n) = tab[0] tab[1] ET trie(tab + 1, n – 1)

Bool trie(int tab[], int n){

if (n < 1) /* Hypothèse de convergence*/exit(1);

if (n == 1) /* condition d’arrêt */return VRAI;

if (tab[0] > tab[1]) /* condition d’arrêt */return FAUX;

/* appel récursif */return trie(tab + 1, n – 1);

}

Il s’agit de programmer le triangle de Pascal dont le prototype obligatoire de la fonction à développer est :

int trigPas(int col, int lig);

Cette fonction reçoit le numéro de la ligne ainsi que le numéro de la colonne et renvoie la valeur contenue dans la case correspondante selon le triangle de Pascal.

ExerciceExercice

ExerciceExercice

Vous devez écrire une fonction récursive pour faire la somme des chiffres d'un nombre entier n ≥0 jusqu’à ce que le résultat soit composé par un seul chiffre.

Par exemple, la somme des chiffres de 854 est 8 (8+5+4=17, 1+7=8).

Le prototype obligatoire de la fonction est :

int sommeChiffres(int n);

C'est toujours assez complexe de suivre un code récursif, mais l'écriture en est plus simple.

La taille de la pile peut augmenter rapidement et, comme l’espace-mémoire réservé pour cette pile est toujours limité, cela peut conduire à un dépassement de sa capacité (stack overflow).

Pour utiliser la récursivité, il faut disposer d'assez de mémoire, par opposition à la méthode d'implémentation itérative.

Exécution d'une fonction récursive

Gestion de la pile : fact(3)

long fact(int n){ long f;

if (n < 0) exit(1);if ( (n == 0) || (n == 1) ) f = 1;else f = n * fact(n-1);return f;

}

typedef struct{ int n;

long f;void *retour;

} TypeEl;

pile

n

f

retour

long fact(int n)

{ long f;if (n < 0) exit(1);if ( (n == 0) || (n == 1) ) f = 1;else f = n * fact(n-1);

return f;}



} TypeEl;


pile

n

f

retour


long fact(int n)

{ long f;if (n < 0) exit(1);if ( (n == 0) || (n == 1) ) f

= 1;else f = n * fact(n-1);

return f;}



} TypeEl;

pile

n

f

retour


long fact(int n)



return f;}



} TypeEl;

pile

n

f

retour


long fact(int n)



return f;}



} TypeEl;

pile

n

f

retour


long fact(int n)



return f;}



} TypeEl;

pile

n

f

retour


long fact(int n)



return f;}



} TypeEl;

pile

n

f

retour


long fact(int n)



return f;}



} TypeEl;

pile

n

f

retour


long fact(int n)



return f;}



} TypeEl;

pile

n

f

retour


long fact(int n)



return f;}



} TypeEl;

pile

n

f

retour


long fact(int n)



return f;}



} TypeEl;

pile


long fact(int n)



return f;}



} TypeEl;

Quand utiliser la récursivité ?

quand il existe une définition récursive claire; (pour les structures de données régulières par exemple)

quand la récursivité est plus simple que la version itérative;

quand on a besoin d'un gain en performance possible grâce à une formulation récursive habile.

La La récursivité

xy = x * xy-1

x0 = 1x1 = x

long exp (int x, int y) {/* . . . . . . . . . . . . . . . */ /* assertion : y >= 0 */ if (y < 0 ) exit(1); if (y == 0) return 1; else

if (y == 1) return x;else return x * exp (x,

y-1);}

Exemple. Gain en performanceExemple. Gain en performance

xy = x y/2 * x y/2, si y pair etxy = x * x y/2 * x y/2, si y impair.

long exp (int x, int y){

/* assertion : y >= 0 */ if (y < 0) exit(1);

if (y == 0) return 1;else if (y == 1) return x; else

if (y % 2 == 0) return exp (x, y/2) * exp (x, y/2);

else return x * exp (x, y/2) * exp (x, y/2);

}

x16 = x8 * x8 (ceci correspondra à un appel)x8 = x4 * x4 (un autre appel)x4 = x2 * x2 (un appel également)x2 (encore un autre appel)

Exemple. Gain en performanceExemple. Gain en performance

La récursivité offre généralement une rapidité et une simplicité dans le développement d’une solution donnée.

Par contre, son principal désavantage est la lourdeur dans l’exécution de cette solution et le temps de mise au point (“débuggage”) qu'elle requiert habituellement.

Quand utiliser la récursivité ?

La La récursivité

Exercices

Rappel

• Expression récursiveExpression récursive du problème (récursion):• L’ « équation » de la récursivité. • Diviser pour régner

• n! = n x (n-1) x (n-2) x (n-3) x … x 1 = n x (n-1)!

• Condition d’arrêtCondition d’arrêt :• Quand est-ce qu’on arrête les appels récursifs?

• 1! ou 0!

• ConvergenceConvergence (vers la condition d’arrêt):• Des conditions qui nous assure qu’un jour on va atteindre les conditions

d’arrêt.• si n = 0 ou n = 1 alors on a les conditions d’arrêt • si n 2 alors la soustraction par 1 nous amènera vers n = 1(n n-1 n-2 n-3 … 2 1)

• donc convergence si n 0


Structure générale d’une fonction récursive :

{if(/* !!condition de convergence */)

exit(1);

if(/*condition d’arrêt*/)return(/*Ce qu’elle doit retourné*/);

elseappel récursif

}

Traitement

long fact(int n){

if (n < 0) exit(1); /* condition de convergence : n 0 */

if (n == 0 || n == 1) return 1l; /* conditions d’arrêt */

else return n * fact(n - 1); /* appel récursif */}

Exemple d’une conception

Écrivez une fonction récursive qui fait l'addition de 2 nombres entiers, n et m, où m est positif ou nul, selon la définition récursive suivante:

add(n,m) = n si m = 0 add(n,m) = 1 + add(n,m-1)

int add(int n, int m) { /* assertion: m>=0 */ if (m < 0) exit(1);

/* cond. d'arrêt: m == 0 */ if (m == 0) return n;

else /* récursion */ return 1+add(n,m-1); }

Écrivez une fonction récursive qui multiplie n par m en additionnant n, m fois.

Par exemple: multiplie(3,4) = 3 + 3 + 3 + 3 = 12.

Vous pouvez supposer que m est positif ou nul, et que m et n sont entiers.

int multiplie(int n, int m) {

/* assertion: m>=0 */ if (m<0) exit(1);

/* cond. d'arrêt: m == 0 */ if (m == 0) return 0;

else /* récursion */ return n+multiplie(n,m-1);

}

Écrivez une fonction récursive qui calcul x exposant y pour y >= 0, sachant que x exposant 0 donne 1, et que x et y sont entiers.

long exp(int x, int y) {

/* assertion: y>=0 */ if( y<0) exit(1);

/* cond. d'arrêt: x exposant 0 == 1 */if (y == 0) return 1l;

else /* récursion */ return (long) (x*exp(x,y-1)); }

Écrivez une fonction récursive qui affiche un tableau d’entier du dernierélément au premier élément (laboratoire#13).

#define MAX 10

void affiche (int t[], int n){

/* assertion: n>1 et n=< MAX */ if (n<=0 || n > MAX) exit (1);

/* cond. d'arrêt: n == 1 */ if (n==1) printf("%d", *t);

else /* récursion */ { affiche(t+1, n-1);

printf(" %d ", *t); } }

Il s’agit d’implanter un algorithme permettant d’afficher le tableau d’entiers suivant d’une certaine manière :

20 15 35 7 18 25 40 3 8 16 19 23 30 37 80

Il est à noter que tout élément du tableau est lié logiquement avec deux autres éléments, le lien1 et le lien2, du même tableau, ainsi:

• le lien1 a comme identificateur 2D• le lien2 a comme identificateur 2D + 1

où D est l'indice de l'élément en question

La récursion à considérer est la suivante:

1. Afficher l’élément lié à e par le lien1;

2. Afficher e;

3. Afficher l’élément lié à e par le lien2;

void affiche(int T[ ], int nb, int i)

{

/* assertion: nb>=0 et 0<= i<nb*/

/*traduire l’assertion..*/

if ( i < nb)

{ affiche(T, nb, 2*i + 1);

printf("%d ", T[i]);

affiche(T, nb, 2*i+2);

}

}

int main(){

int tab[]={ 20, 15, 35, 7, 18, 25, 40, 3, 8, 16, 19, 23, 30, 37, 80};

affiche(tab, 15, 0);

return 0;}


{



if ( i < nb)

{ affiche(T, nb, 2*i + 1);


printf("%d ", T[i]);

}

}

int main(){

int tab[]={ 20, 15, 35, 7, 18, 25, 40, 3, 8, 16, 19, 23, 30, 37, 80};


return 0;}


{



if ( i < nb)

{ printf("%d ", T[i]);

affiche(T, nb, 2*i + 1);


}

}

int main(){

int tab[]={ 20, 15, 35, 7, 18, 25, 40, 3, 8, 16, 19, 23, 30, 37, 80};


return 0;}

Ré-écrivez la fonction strlen() sous une forme récursive (laboratoire#13).

#include <stdio.h>

#define OK 1

int longueur(char *c, int *err)

{

/*A: c est une chaîne de caractères*/

*err=OK;

if (*c!= '\0')

{

return 1+ longueur(c+1, err);

}

return 0;

}int main()

{

char c[]="Bonjour";

int err;

printf("\n %d \n\n", longueur(c, &err));

return 0;

}

Écrivez une fonction récursive qui renverse une chaîne de caractères.

Exemple:

la chaîne « Bonjour » doit être transformée en « ruojnoB ».

void miroir(char *c, int l1, int l2)

{

char car;

if (*(c+l1)!= '\0')

{

car= *(c+l1);

miroir(c,l1+1,l2-1);

*(c+l2-1)= car;

}

}

int main(){

char c[]="Bonjour toi !";

miroir(c, 0, strlen(c));

printf("\n C: %s \n\n", c);

return 0;}

Écrivez une fonction récursive qui compte le nombre de chiffres que composent un nombre entier n ≥ 0.

Le prototype obligatoire est :int longueur (int n);

Exemple : si n = 78945, la fonction doit retourner 5 (78945 est composé de 5 chiffres).

Utilisez la fonction exit() pour l’éventuelle gestion de ou des pré-conditions à l’exécution de la fonction.

int longueurNombre (int n){

if (n<0) exit(1);

if (n <=9) return 1;else return(1+longueurNombre(n/

10));}

Il s’agit de programmer le triangle de Pascal dont leprototype obligatoire de la fonction à développer est :

int trigPas(int col, int lig);

Cette fonction reçoit le numéro de la ligne ainsi que le numéro de la colonne et renvoie la valeur contenue dans la case correspondante selon le triangle de Pascal.

int trigPas (int x, int y){

if(x<=0 || y<=0) exit(1);if ( x == 1 || /*point d'appui : la première colonne

*/y == x) /* point d'appui : la diagonale

*/ return 1; else return (trigPas(x, y - 1) + trigPas (x - 1, y - 1)); /*appel récursif */}

int main(){ int ligne, colonne; for (ligne= 1; ligne <=15; ligne++) {

for (colonne = 1; colonne <= ligne; colonne++) {

printf (" %d ", comb(colonne, ligne));

} printf("\n");

}return 0;}

Soit la fonction suivante :

int f(int m, int n){

if(m == 0)return(n + 1);

if(n == 0)return f(m – 1, 1);

return f(m – 1, f(m, n – 1));}

Faites une trace (l’arbre des appels récursifs) pour m = 1, n = 3.

Vous devez écrire une fonction récursive pour faire la somme des chiffres d'un nombre entier n ≥0 jusqu’à ce que le résultat soit composé par un seul chiffre.

Par exemple, la somme des chiffres de 854 est 8 (8+5+4=17, 1+7=8).

Le prototype obligatoire de la fonction est :

int sommeChiffres(int n);

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

int sommeChiffres(int n){

if(n<0) exit(1);

if(n <= 9) {

return n; /*Condition d'arrêt: c'est un chiffre*/}else /*C'est un nombre, on recommence*/{

return sommeChiffres(n%10 + sommeChiffres(n/10));

}}

int main() /*pour tester*/{

printf("%d\n", sommeChiffres(789));return 0;

}

Documents

Programme de baccalauréat en informatique Algorithmique et programmation IFT-17582 Abder Alikacem Abder Alikacem Semaine 13 La récursivité Département