1 La récursion. Nous avons vu qu'un programme est constitué d'un ensemble de fonctions....

La récursion

• Nous avons vu qu'un programme est constitué d'un ensemble de fonctions.

• Il est possible pour une fonction donnée d'appeler une autre fonction.

• Que se passe-t-il si une fonction s'appelle elle-même?

• C'est ce que l'on appelle la récursion.

• Question: Écrire un programme qui calcule le nombre de Fibonacci défini comme suit:

1 n si ;

FFF nnn

#include <iostream> int fibona(int); int main() { cin << n; cout <<‘’le ‘’<<n<<‘’ ème nombre est’’; cout << fibona(n); return (0); }int fibona(int n) {int ans; if n < 2 ans = n; else ans = fibona(n-1) + fibona(n-2); return (ans); }

Cette fonction est valide: aucune règle n'interdit à une fonction de s'appeler elle-même.

Définition: Une procédure est dite récursive si elle fait appel à elle-même (directement ou indirectement).

Fonctionnement d’une fonctionrécursive

• Création d’une pile pour la sauvegarde entre autres des paramètres d’appels de la procédure

• Calculer n!

• Description du problème: Calculer le factorielle d'un nombre entier donné en entrée.

• Entrée: Un nombre entier plus grand ou égal à 0.

• Sortie: Un nombre entier.

• Fonction principale

• entier n nfact• lire n • nfact factoriel(n)• écrire “la factorielle de ” n “est” nfact

• où factoriel satisfait le prototype

• entier factoriel(entier)

• entier n nfact• lire n • si (n < 0) alors écrire “entrée négative: ” n• sinon• nfact factoriel(n)• écrire “la factorielle de ” n “est” nfact

• où factoriel satisfait le prototype

• entier factoriel(entier)

Analyse de la fonction factoriel

0! = 11! = 12! = 2*1 = 23! = 3*2*1 = 64! = 4*3*2*1 = 24n! = n*(n-1)*(n-2)*…*2*1 = n* (n-1)! 1 si n 1n!= n * (n-1)! sinon

Fonction factoriel

Entête:entier factoriel(entier n)

Corps:si (n 1) retourner 1retourner n * factoriel(n-1)

Pas-à-pas avec n=4

entier n nfactlire n si (n < 0) alors écrire “entrée négative: ” nsinon nfact factoriel(n) écrire “la factorielle de ” n “est” nfact

entier n nfact

entier n nfactlire n nfactsi (n < 0) alors écrire “entrée négative: ” nsinon nfact factoriel(n) écrire “la factorielle de ” n “est” nfact

lire n

entier n nfactlire nsi (n < 0) alors écrire “entrée négative: ” nsinon nfact factoriel(n) écrire “la factorielle de ” n “est” nfact

si (n < 0) alors écrire “entrée négative: ” n

entier

entier n nfactlire nsi (n < 0) alors écrire “entrée négative: ” nsinon nfact factoriel(n) écrire “la factorielle de ” n “est” nfact nfact factoriel(n)

entier

n entier

si (n 1) retourner 1retourner n * factoriel(n-1)

si (n 1) retourner 1retourner n * factoriel(n-1)si (n 1) retourner 1

entier

n entier

si (n 1) retourner 1retourner n * factoriel(n-1)retourner n * factoriel(n-1)

entier

n entier

entier

n entier

si (n 1) retourner 1

n entier

entier

n entier

retourner n * factoriel(n-1)

n entier

entier

n entier

entier

n entier

entier

si (n 1) retourner 1

entier

n entier

entier

retourner n * factoriel(n-1)

entier

n entier

entier

n entier

entier

si (n 1) retourner 1retourner n * factoriel(n-1)si (n 1) retourner 1

entier

n entier

si (n 1) retourner 1retourner n *1

n entier

entiern

retourner n * 1

entier

n entier

retourner n * 2

si (n 1) retourner 1retourner n * factoriel(n-1)retourner n * 6

entier

entier nfact 24

nfact écrire “la factorielle de ” n “est” nfact

entier

est 24

La factorielle de 4 est 24

Comment le faire en C#include <iostream>int fact(int) /* prototype de la fonction*/int main(){ int n; cin >> n; if (n < 0) cout <<‘’nombre négatif‘’; else cout << fact(n); return (0); }int fact(int n) /* définition de la fonction*/ { if (n < 2) return (1); else return (n*fact(n-1)); }

Test d’arrêt

Le test d’arrêt

• La récursion (appels de la fonction à elle-même) doit s’arrêter à un moment donné (test d’arrêt). Autrement, l’exécution va continuer indéfinement.

Exemple

void exemple(){ cout << "La recursion\n"; exemple();}

Exemple 2: Lire et afficher un nombre arbitraire d'entiers

• Description du problème: Lire un entier n suivit de n autres entiers que l'on doit afficher à l'écran.

• Entrée: Un entiers positif n suivi de n entiers séparés par un ou plusieurs caractères d'espacement.

• Sortie: n entiers, un par ligne.

• Exemple

• Sur l'entrée: 3 45 123 67

• le programme doit afficher:

• 45

• 123

• 67

Fonction principale

• entier n • lire n • copier(n)

• où copier satisfait le prototype

• copier(entier)

• Fonction copier

• Entête:

• copier(entier n)

• Corps:

• Copier la première valeur

• Copier les n-1 autres valeurs

• Fonction copier

• Entête:• copier(entier n)• Corps:• si (n < 1) retourner Il n'y a rien à lire• sinon• Copier la première valeur• Copier les n-1 autres valeurs

• Fonction copier

• Entête:• copier(entier n)• Corps:• entier x• si (n < 1) retourner Condition d'arrêt• sinon• lire x• ecrire x• copier(n-1) Copier les n-1 valeurs

suivantes

#include <iostream>void copier(int); /* prototype de la fopnction */main(){ int n; cin>>n; copier(n); }void copier(int n){ int x; if (n < 1) return; /* S'il n'y a plus rien a lire. */ cin>>x; /* Copier la premiere valeur. */ cout<<x<<endl; copier(n-1); /* Copier les valeurs suivantes. */ }

Comment le faire en C

• Inverser l'ordre des entiers lus

• Description du problème: Refaire le problème précédent

• mais cette fois en affichant les valeurs dans l'ordre inverse.

• Entrée: Un entiers positif n suivit de n entiers séparés par un ou plusieurs caractères d'espacement.

• Sortie: n entiers, un par ligne.

• Exemple

• Sur l'entrée: 3 45 123 67

• le programme doit afficher:

• 67

• 123

• 45

• entier n • lire n • invcopier(n)

• où invcopier satisfait le prototype

• invcopier(entier)

Fonction copier de précédente

• Entête:• copier(entier n)• Corps:• entier x• si (n < 1) retourner Condition d'arrêt• sinon• lire x• ecrire x• copier(n-1) Copier les n-1 valeurs

suivantes

• Fonction invcopier

• Entête:• invcopier(entier n)• Corps:• entier x• si (n <= 0) retourner Condition d'arrêt• sinon• lire x Lire la première valeur• invcopier(n-1) Copier les n-1 valeurs

suivantes• ecrire x Écrire la première valeur

Comment le faire en C#include <iostream>void copier(int); /* prototype de la fopnction */main(){ int n; cin >> n invcopier(n); } void invcopier(int n){ int x; if (n <= 0) return; /* Condition d'arrêt */ else{ cin >> x; /* Lire la première valeur */ invcopier(n-1); /* Copier les n-1 valeurs suivantes */ cout << x; /* Écrire la première valeur */ }

Trouver le maximum

• Description du problème: Lire un entiers n puis trouver le maximum des n entiers suivants lus en entrée.

• Entrée: Un entiers positif n suivit de n entiers séparés par un ou plusieurs caractères d'espacement.

• Sortie: Un entier représentant le maximum.

• Exemple

• Sur l'entrée: 10 45 123 67 36 1 67 13 44 9 99

• le programme doit afficher: 123

• entier n maxi • lire n • maxi = maximum(n)• écrire maxi

• où maximum satisfait le prototype

• entier maximum(entier)

• Fonction maximum

• Entête:• entier maximum(entier n)• Corps:• entier x y• lire x• y le maximum des n-1 valeurs suivantes• retourner le maximum entre x et y•

• Entête:• entier maximum(entier n)• Corps:• entier x y• lire x• y maximum(n-1)• retourner max(x,y)

• où max est une fonction satisfaisant le prototype suivant:

• entier max(entier, entier)

• Fonction max

• Entête:• entier max(entier a, entier b)• Corps:• si (a > b) alors• retourner a• sinon • retourner b

• Entête:• entier maximum(entier n)• Corps:• entier x y• lire x• si (n=1) alors retourner x (condition d'arrêt)• sinon• y maximum(n-1)• retourner max(x,y)

• où max est une fonction satisfaisant le prototype suivant:

• entier max(entier, entier)

Comment le faire en C#include <iostream>int maximum (int); /* prototype de la fopnction */int max(int,int);main(){ int n, maxi; Cin >> n maxi = maximum(n) cout << maxi;} int maximum(int n){ int x, y; cin >> x; if (n=1) retunrn(x); /*(condition d'arrêt) */ else { y = maximum(n-1) return max(x,y); }} /* fin de la fonction */int max(int x, int y){ if (x > y) return(x); else return(y);}

Le PGCD de deux nombres

• Description du problème: Calculer le plus grand commun diviseur entre deux entiers.

• Entrée: Deux entiers x et y

• Sortie: Un entier représentant le pgcd entre x et y

• En reprenant l’algorithme qu’on a vu précédemment, la stratégie suvie est comme suit (on suppose que x > y):

• Si y divise x alors x est le PGCD de x et y• Sinon, le pgcd de ces deux nombres est le

même que celui de y et de x modulo y. • Autrement dit, on peut définir le PGCD de

x et Y comme suit:

• PGCD(x,y) = y si s mod y = 0• PGCD(x,y) = PGCD(y, x modulo y) sinon.

A partir de cette définition, on obtient la fonction suivante:

entier PGCD (entier x, entier y) entier tmp; si x % y = 0 tmp = y; conditon d’arrêt sinon tmp = PGCD(y,x % y); retourner (tmp);

En C, on obtient:#include <iostream>int PGCD (int,int); /* prototype de la fonction */main(){ int x,y; cin >> x>>y; cout << PGCD(x,y);} int PGCD(int x, int y){ int tmp; if (x % y == 0) tmp = y; conditon d’arrêt else tmp = PGCD(y,x % y); return (tmp);} /* fin de la fonction */

Les tours de Hanoï

• Description du problème: Montrez comment déplacer n disques de tailles distinctes d'une tige A vers une tige B

• en utilisant comme tampon une tige C. Initialement seule la tige A contient les n disques ordonnés avec le plus petit sur le dessus. On ne doit déplacer qu'un seul disque à la fois. Il est interdit de placer un disque sur un autre plus petit.

• Entrée: Un entier n représentant le nombre de disques.

• Sortie: Une série d'instructions de la forme " déplacer i vers j" indiquant les déplacements nécessaires pour résoudre le problème.

• entier n• lire n• hanoi(n,1,2,3)

• où hanoi satisfait le prototype

• hanoi(entier, entier, entier, entier)

• Supposons qu’on sache comment déplacer les (n-1) derniers disques de la tour 1 vers la tour 2, en utilisant la tour 3.

• déplacer le disque restant de la tour 1 vers la tour 2

• déplacer maintenant les (n-1) disques de la tour 3 vers la tour 2, en s’aidant de la tour 1.

• Fonction hanoi

• Entête:• hanoi(entier n, entier i, entier j, entier k)• (Affiche les instructions pour déplacer n disques • de la tige i vers la tige k)• Corps:• si (n > 0)• {• hanoi(n-1, i, k, j)• écrire "Déplacer i vers k);• hanoi(n-1, j, i, k)• }

En C on obtient:#include <iostream.h>void hanoi (int,int,int,int)} /* fin de la fonction */main(){ int n; cin>>n; hanoi(n,1,2,3);}void hanoi(int n,int i,int j,int k) { if (n>0) { hanoi(n-1,i,k,j); cout <<“déplacer le disque de haut de la tour<<i<<“ à la tour “<<k; hanoi(n-1,j,k,i); }

Exemple avec n = 4 disques:

• On obtient la série d’affichages suivants:• Déplacer le disque de haut de la tour 1 à la tour 2• Déplacer le disque de haut de la tour 1 à la tour 3• Déplacer le disque de haut de la tour 2 à la tour 3• Déplacer le disque de haut de la tour 1 à la tour 2• Déplacer le disque de haut de la tour 3 à la tour 1• Déplacer le disque de haut de la tour 3 à la tour 2• Déplacer le disque de haut de la tour 1 à la tour 2• Déplacer le disque de haut de la tour 1 à la tour 3• Déplacer le disque de haut de la tour 2 à la tour 3• Déplacer le disque de haut de la tour 2 à la tour 1• Déplacer le disque de haut de la tour 3 à la tour 1• Déplacer le disque de haut de la tour 2 à la tour 3• Déplacer le disque de haut de la tour 1 à la tour 2• Déplacer le disque de haut de la tour 1 à la tour 3• Déplacer le disque de haut de la tour 2 à la tour 3

Résumé

Les composantes d'une fonction récursive

si (condition d'arrêt) alors instructions sans appel récursifsinon instructions pouvant contenir un ou plusieurs appels récursifs (au moins un des paramètres d'appel est "décrémenté ou incrémenté dans le but de se diriger vers la condition d’arrêt").

1 La récursion. Nous avons vu qu'un programme est constitué d'un ensemble de fonctions....

Documents

29/9/2005 © 2005 P. Van Roy. All rights reserved. 1 FSAB 1402: Informatique 2 Récursion sur les Entiers Peter Van Roy Département dIngénierie Informatique,

Établissements (écoles, collèges, lycées, universités…) Fonction administrative Fonction éducative Fonction pédagogique Environnement Numérique de Travail

Les enjeux des entreprises en forte et hyper croissance · La fonction marketing et commerciale La fonction R&D / Innovation La fonction production La fonction finance et comptabilité

Publication semestrielle de la Commission Prévention … · 2017-07-03 · convenu d'appeler les Règles de l'art et en l'ab-Prévention des désordres liés aux produitset procédés

fonction finance.pdf

Fiche mémo fonction vectoriellelutes.upmc.fr/physique/mp/5_integrales/5_rappels_cours... · Web viewFiche mémo fonction vectorielle Primitive d’une fonction continue. Intégrale

Fonction d’étayage et fonction contenante

fonction logistique

12/10/2004 P. Van Roy, InfoT4, S3 1 Informatique T4 (FSA1450) Récursion sur les entiers Peter Van Roy Département d’Ingénierie Informatique, UCL pvr@info.ucl.ac.be

DROIT CONSTITUTIONNEL · 2018-10-08 · 4 ci peuvent être recherchés et punis. Et c'est l'avantage de ce gouvernement sur celui de Gnide, où la loi ne permettant point d'appeler

Stock Fonction

IV. - TUNISIE - AANaan.mmsh.univ-aix.fr/Pdf/AAN-1977-16_18.pdfIV. - TUNISIE En Tunisie, l'année 1977 a pris fin le 26 janvier 1978 avec ce qu'il est convenu depuis d'appeler le «Jeudi

CONTROLE DE FONCTIONNEMENT - worldradiohistory.com€¦ · piexe. Les poster a une memoire permettent d'appeler, par action sur une seule touche, le dernier nuttier° compose, si

Question - ITU€¦ · Web viewLes appels des appelants choisissant "d'appeler" par courrier électronique ou par l'intermédiaire d'un site de discussion sur le web peuvent être

Récursion IFT1025: Programmation 2 Jian-Yun Nie. Définition Le fait pour un programme ou une méthode de s'appeler lui-même. Par exemple –Définir la notion

Le régime de retraite de la fonction Publique Fédérale fonction Publique Fédérale Le régime de retraite de la fonction Publique Fédérale fonction Publique

Modèle conceptuel - drisshazzaf.typepad.comdrisshazzaf.typepad.com/oracle/files/SQL.pdf · Contrairement à la notion de fonction monoligne, une fonction multiligne ou fonction de

fonction logique

Notion de fonction. Résolution graphique. Fonction affine. · 2 1 Fonction numérique 1.1 Introduction Pour le néophyte ou « l’homme de la rue », la notion de fonction n’est

CSI1502 Introduction au génie logiciel Chapitre 11: Récursion