# TP et application du cours :

## Exercice 1 :

def f(x,y):
    if x == y : 
        return x
    elif x<y : 
        return f(x, y-x)
    else : 
        return(x-y, y)

1. Sans exécuter le code, indiquer ce que renvoient f(5,15) et f(8,20) ?

f(5,15) renvoie 5
f(8,20) renvoie 4

2. Indiquer plus généralement ce que calcule f(x,y).

Plus généralement, f(x,y) renvoie le PGCD de x et y.

## Exercice 2 :

Soit f(x) une fonction récursive. Quelles affirmations sont correctes ?

1. x doit être un entier. FAUX
2. Pour tout appel f(y) contenu dans la définition de f(x), on doit avoir y<x. FAUX
3. Il ne doit pas y avoir de chaîne infinie x₁, x₂, …, x_i, … telle que pour tout i, f(x_i) nécessite le calcul de f(x_i+1). VRAI
4. Pour certaines valeurs de x, f(x) peut elle-même faire au moins un appel à f. FAUX (elle fait obligatoirement un appel à elle-même sinon elle n'est pas récursive)
5. Il doit exister au moins une valeur y pour laquelle f(y) ne fait aucun appel récursif à f. VRAI (sinon on pas de cas d'arrêt = boucle infinie)

## Exercice 3 :

Donner une définition récursive qui correspond au calcul de la fonction factorielle n! = 1x2x3x...x n si n > 0 et 0! = 1, puis le code d’une fonction fact(n) qui implémente cette définition.

Définition récursive fonction factorielle :
- La fonction factorielle d'un nombre n
- si n=0 vaut 1
- si n>=1 veut n multiplié la factorielle de n

def fact(n):
    if n==0:
        return 1
    else:
        return n*fact(n-1)

## Exercice 4 :

Donner une définition récursive qui correspond au calcul de la suite de Fibonacci puis le code d’une fonction fibo qui implémente cette définition.

Définition récursive fonction fibo :
- U₀=0
- U₁=1
- U_n+1=U_n-1+U_n-2

def fibo(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fibo(n-1)+fibo(n-2)

## Exercice 5 :

Soit Un la suite d’entiers définie par :

- Un+1 = Un/2 si Un est pair
- Un+1 = 3*Un+1 si Un est impair
- avec U0 un entier quelconque plus grand que 1.

Écrire une fonction syracuse(u_n) qui affiche les valeurs successives de la suite Un tant que Un est plus grand que 1.

def syracuse(u_n):
    if u_n<=1:
        print(u_n)
    else:
        if u_n%2==0:
            print(u_n)
            return syracuse(u_n/2)
        else:
            print(u_n)
            return syracuse(3*u_n+1)

## Exercice 6 : Passer de l’itératif au récursif

Écrire une fonction affichage_iteratif qui affiche les entiers de k à n (avec k et n pris en paramètre).

def affiche_iteratif(k,n):
    for i in range(k,n):
        print(i)

Proposer une version récursive affichage_recursif effectuant la même tache.

def affiche_iteratif(k,n):
    if k==n:
        print(k)
    else : 
        print(k)
        return affiche_iteratif(k+1,n)

## Exercice 7 :

Le PGCD est le plus grand commun diviseur de deux entiers.

Proposer une version différente de celle de l’exercice 1.

Pour déterminer le PGCD de deux entiers n1 et n2, quels sont les opérateurs arithmétiques à utiliser ?
_division eucldienne + nombres premiers

Écrire la définition d’une fonction récursive permettant de déterminer le PGCD de deux entiers pris en paramètre.

Implémenter cette fonction en Python.