Thème 4

Récursivité

Activité

Activité

Activité

Activité

Activité

Activité

Décrire la situation, en précisant quels sont les éléments qui ont permis à notre personnage de déterminer le prix du livre.

La somme des nombes de 1 à $N$

Somme des nombres de 1 à n

Écrire une fonction qui prend en paramètre un entier naturel n (n > 0) et renvoie la somme des entiers de 1 à n.

Défie

Même question, mais aucune autre variable que le paramètre ne doit-être créée.


def somme(n):

 
def somme(n):
    if n == 1:
        return 1

 
def somme(n):
    if n == 1:
        return 1
    else:
        return n + somme(n - 1)

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5)

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))
            5 + (4 + (3 + (2 + somme(1))))

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))
            5 + (4 + (3 + (2 + somme(1))))
            5 + (4 + (3 + (2 + (1 + somme(0)))))

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))
            5 + (4 + (3 + (2 + somme(1))))
            5 + (4 + (3 + (2 + (1 + somme(0)))))
            5 + (4 + (3 + (2 + (1 + (0)))))

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))
            5 + (4 + (3 + (2 + somme(1))))
            5 + (4 + (3 + (2 + (1 + somme(0)))))
            5 + (4 + (3 + (2 + (1 + (0)))))
            5 + (4 + (3 + (2 + (1))))

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))
            5 + (4 + (3 + (2 + somme(1))))
            5 + (4 + (3 + (2 + (1 + somme(0)))))
            5 + (4 + (3 + (2 + (1 + (0)))))
            5 + (4 + (3 + (2 + (1))))
            5 + (4 + (3 + (3)))

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))
            5 + (4 + (3 + (2 + somme(1))))
            5 + (4 + (3 + (2 + (1 + somme(0)))))
            5 + (4 + (3 + (2 + (1 + (0)))))
            5 + (4 + (3 + (2 + (1))))
            5 + (4 + (3 + (3)))
            5 + (4 + (6))

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))
            5 + (4 + (3 + (2 + somme(1))))
            5 + (4 + (3 + (2 + (1 + somme(0)))))
            5 + (4 + (3 + (2 + (1 + (0)))))
            5 + (4 + (3 + (2 + (1))))
            5 + (4 + (3 + (3)))
            5 + (4 + (6))
            5 + (10)

Regardons ce que fait un appel à cette fonction avec comme argument 5.


somme(5) => 5 + somme(4)
            5 + (4 + somme(3))
            5 + (4 + (3 + somme(2)))
            5 + (4 + (3 + (2 + somme(1))))
            5 + (4 + (3 + (2 + (1 + somme(0)))))
            5 + (4 + (3 + (2 + (1 + (0)))))
            5 + (4 + (3 + (2 + (1))))
            5 + (4 + (3 + (3)))
            5 + (4 + (6))
            5 + (10)
            15

Récursivité

On dira d'une fonction qu'elle est récursive si cette fonction s'appelle elle-même.
C'est à dire que dans définition de la fonction, on fait un appel à cette fonction.

Attention

Cette définition a elle seule, ne permet pas de présumer de la validité du code de la fonction.

La fonction problème

La fonction `problème`

Condition de terminaison

Pour être sûr qu'une fonction récursive va se terminer, il faut que :

la fonction contienne une condition d'arrêt
chaque appel à la fonction se rapproche de la condition d'arret. Généralement, les appels successifs se font à l'aide d'un entier décrémenter.

Exercice 1

On considère la fonction mystere qui prend en paramètre un nombre entiers naturel n définit par le code ci‐dessous.


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

La fonction mystere est‐elle récursive ? Justifier.
Déterminer la relation de entre mystere(n) et mystere(n-1)
Complète la pile d’éxécution de l’appel mystere(4).
Combien d’appels à la fonction l’appel initial déclenche‐t‐il ?

Exercice 2 Algorithme d’Euclide

On considère la fonction pgcd qui prend en paramètre deux entiers, a et b, tel que a>b et qui renvoie le pgcd (plus grand diviseur commun) de a et de b.


def pgcd(a,b):
    if a % b == 0
        return b
    else:
        return pgcd(b, a % b)

La fonction pgcd est‐elle récursive ? Justifier
Quelle est la condition d’arret de la fonction pgcd ?
Quelle valeur va retourner l’appel à la fonction pgcd(24,18) ? Combien d’appels à la fonction l’appel initial déclenche‐t‐il ?

Exercice 2 Algorithme d’Euclide

On considère la fonction pgcd qui prend en paramètre deux entiers, a et b, tel que a>b et qui renvoie le pgcd (plus grand diviseur commun) de a et de b.


def pgcd(a,b):
    if a % b == 0
        return b
    else:
        return pgcd(b, a % b)

La fonction pgcd est‐elle récursive ? Justifier
Quelle est la condition d’arret de la fonction pgcd ?
Quelle valeur va retourner l’appel à la fonction pgcd(24,18) ? Combien d’appels à la fonction l’appel initial déclenche‐t‐il ?

Titre du popup

Message du popup !