Évaluation récursivité

Eval 03
Consignes
  • Cette évaluation se déroule en deux parties:
    • Exercice 1 et 2 premières questions de l’exercice 2 sur papier.
    • Fin exercice 2 et et exercice 3 sur machine.
  • La partie papier est à réaliser en premier. Une attention particulière sera portée sur la présentation, la syntaxe et l’orthographe. Pour la seconde partie:
    • Créer un dossier eval-03-votrenom
    • Écrire chaque fonction dans un fichier différent.
    • Documenter les fonctions.
    • Compresser le dossier et le déposer dans le casier du professeur.

Exercice 1 SUR PAPIER

def operation(x: int, y: int) -> int:
    if x == 0:
        return 0
    elif x % 2 == 0:
        return operation(x//2, y+y)
    else:
        return operation(x//2, y+y) + y

operation(5, 2)
  1. Donner, dans l’ordre, les différents appels récursifs effectués lors de l’appel principal:
operation(5, 2)
  1. Donner la valeur renvoyée par l’appel:
operation(5, 2)
  1. Que fait cette fonction?

Exercice 2

  1. En Python, comment vérifier qu’un nombre est multiple de 3 (divisible par 3)?
  2. Combien vaut la somme de tous les multiples de 3 inférieurs ou égaux à 10?
  3. Écrire la fonction multiple3(n: int) -> int qui renvoie la somme de tous les multiples de 3 inférieurs ou égaux à n.
  4. Écrire deux assertions pour tester la fonction.

Exercice 3

Soit $u_n$ la suite d’entiers définie par:

$$ u_{n} = \left\lbrace \begin{array}{ll} 0 & si~n=0\\\\ 1 & si~n=1\\\\ u_{n-2}-u_{n-1} & \forall n\geq2\\\\ \end{array} \right. $$
  1. Écrire la fonction récursive suite(n: int) -> int qui renvoie le n-ième terme de la suite.
  2. Écrire deux assertions pour tester la fonction.