Terminale - Récursivité

Exercices

Conjecture de Syracuse

On considère la fonction récursive suivante :

def f(a):
    if a == 1:
        return 1
    else:
        if a % 2 == 0:
            return f(a // 2)
        else:
            return f(3*a + 1)
  1. Calculer (à la main !) f(3) et f(40).
  2. Est-on certain que la fonction précédente se termine ?
  3. Écrire un programme Python permettant de calculer les valeurs de f(a) pour a allant de 1 à 10 000.
    Vérifier que ce programme se termine.
En septembre 2026, personne n’a réussi à trouver une valeur de $a$ pour laquelle $f(a)$ génère une boucle infinie... Les mathématiciens pensent qu’une telle valeur n’existe pas : c’est la conjecture de Syracuse.
Puissance d'un nombre

Écrire une fonction récursive puissance(x,y) qui retourne la valeur de $x^y$ (où x et y sont deux nombres en- tiers naturels), sans utiliser l’opération **.

>>> puissance(2,3)
8
On basera l'appel récursif sur la formule $x^{n} = x \times x^{n-1}$ et le cas de base sur le fait que $x^0 = 1$.
Somme des entiers

Écrire une fonction récursive somme(n) qui retourne la somme des entiers de 1 à $n$.

>>> somme(6) # Renvoie 1 + 2 + 3 + 4 + 5 + 6
21
On basera l'appel récursif sur la formule $S_n = S_{n-1} + n$ où $S_n = 1 + 2 + 3 + \ldots + n$.
Factorielle d'un entier naturel

Écrire une fonction récursive factorielle(n) qui retourne la factorielle du nombre $n$, définie comme $n! = 1 \times 2 \times 3 \times \ldots \times n$. Par convention, on a $0! = 1$.

>>> factorielle(5) # Renvoie 1*2*3*4*5
120
On basera l'appel récursif sur la formule $n! = n \times (n-1)!$.
Divisibilité par 3
  1. Compléter la fonction suivante, dont le but est de retourner la somme des chiffres d'un nombre, de façon récursive : 
    def somme_chiffres(n):
    if n <= 9:
        return n
    else:
        return somme_chiffres(...) + ...
    Il est fortement conseillé d'utiliser les opérations // et %.

  2. Pour savoir si un entier est divisible par 3, on dispose du critère de divisibilité bien connu :

    Un nombre est divisible par 3 si la somme de ses chiffres est encore divisible par 3

    Écrire une fonction récursive divisiblePar3(n) qui retourne True si n est divisible par 3, et False sinon.

    >>> divisiblePar3(123456789)
    True
Sommaire