Contraintes : nous n’utiliserons pas de boucle (ni for ni while).

Exercices

1. Écrire la fonction puissance.
2. En utilisant puissance, écrire la fonction exponentielle binaire (n \mapsto 2^n)
3. Écrire la fonction factorielle.
4. Écrire la fonction sommielle.
5. Écrire une fonction qui calcule le n-ième terme de la suite de Fibonacci.
   1. La tester sur l’entrée 30 (on devrait trouver 832040)
   2. La tester sur les valeurs suivantes. Mesurer le temps utilisé.
6. Écrire des fonctions pair et impair qui testent si un nombre est pair ou impair.
7. Écrire une fonction combinaison qui calcule les combinaisons de k éléments parmi n en utilisant une identité connue du triangle de Pascal.
8. Écrire la fonction de Ackermann.
   1. La tester sur l’entrée (3,0)
   2. La tester sur l’entrée (3,6)
   3. La tester sur l’entrée (3,7)
   4. La tester sur l’entrée (4,0)
   5. La tester sur l’entrée (4,1)