Exercice 1 : Ecrire une fonction récursive PGCD qui retourne le PGCD de 2 entiers A et B en utilisant le principe d’Euclide.              

Exercice 2 : Ecrire une fonction récursive combinaison qui calcule le nombre de combinaisons de p éléments pris parmi n éléments différents par la formule suivante :

                              =n           =1

                                =+

Exercice 3 :

1-      Écrire une fonction récursive calculant la suite de Fibonacci. 

Exercice 4 : fonction d’Ackermann

Ecrire une fonction récursive Ack qui calcule Ack(m,n) selon la formule suivante :

        Ack(0,n) = n + 1.

        Si  m>0 et n=0 Ack(m-1,1).

        Sinon Ack(m-1,A(m, n-1)).

Exercice 5:

fonction 91 de MacCarthy est une fonction récursive définie par McCarthy dans son étude de propriétés de programmes récursifs, et notamment de leur vérification formelle. 

Ecrire une fonction récursive f qui calcule f selon la formule suivante :

f = n - 10  Si n > 100

f = f(f(n+11))  Sinon

-          Calculer f(96).

Exercice 6:

fonction de Morris

Soit la fonction récursive suivante :

Fonction g(m, n : Entier) : Entier

Début

Si(m = 0) Alors g ß1

Sinon g ßg(m – 1,g(m,n))

FinSi

Fin

-          Calculer g(1,0).

Exercice 7 :

Ecrire une fonction récursive qui permet de réaliser une recherche dichotomique des éléments d’un tableau.

Exercice 8 :

Ecrire une fonction récursive qui permet de trouver le maximum d’un tableau des entiers.

Exercice 9 :

Ecrire une procédure récursive qui permet de réaliser le tri par fusion

Exercice 10 :

Transformer l’algorithme trie par shell réalisé précédemment sous forme de fonction et procédure récursive.