WikiMath

Calcul du PGCD de deux entiers naturels

Etant donnés deux entiers positifs $a$ et $b$, on appelle PGCD de $a$ et $b$ le plus grand diviseur commun aux entiers $a$ et $b$. On le note PGCD$(a,b)$.
Pour calculer efficacement un PGCD, on utilise l'algorithme d'Euclide (ou méthode des divisions successives) qui repose sur la propriété suivante :

Si $b=0$ alors PGCD$(a,b)=a$
sinon PGCD$(a,b)=$PGCD$(b,r)$ où $r$ désigne le reste de la division euclidienne de $a$ par $b$.

1. Calculer "à la main" PGCD(160,108) en posant trois divisions.
2. Ecrire une fonction récursive pgcd(a,b) qui renvoie le PGCD de $a$ et $b$.
3. Tester cette fonction pour obtenir PGCD(35874,10926).

Récursivité terminale

1. En effectuant une recherche sur internet, proposer une définition de la "récursivité terminale" (ou "tail recursion" en anglais)
2. Parmi les fonctions récursives étudiées au TP6, quelles sont celles qui sont récursives terminales ?
3. Que fait la fonction Python suivante ?

def mystere(n,res)

    if n<=1:
        return res
    else:
        return mystere(n-1,n*res)

Suite de Fibonacci

Proposer un algorithme récursif terminal permettant de calculer le $n$-ième terme $F_n$ de la suite de Fibonacci étudiée au TP6.