EnglishCommencer

Récurrence et récursivité

Le raisonnement par récurrence (initialisation, hérédité, conclusion ; récurrence simple et forte) et son jumeau en programmation : cas de base et appel récursif, terminaison et correction d'une fonction récursive.

  • 27 cartes
  • 5 thèmes
  • Gratuit
Réviser ce deck

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

  1. Notions
  2. Questions
  3. Ranger et relier
  4. Mises en situation
  5. Comprendre

Quelques cartes du deck

  • Raisonnement par récurrence : de quoi s'agit-il ?

    Voir la réponse

    Démonstration d'une propriété pour tous les entiers à partir d'un rang donné : on la vérifie au premier rang, puis on prouve qu'un rang vrai entraîne le suivant.

    C'est l'image des dominos : le premier tombe, et chaque domino qui tombe fait tomber le suivant, donc tous tombent.

  • Qu'affiche ce programme ?

    ```python
    def f(n):
    if n == 0:
    return 1
    return n * f(n - 1)

    print(f(4))
    `

    • 24
    • 10
    • 120
    • 6
    Voir la réponse

    24

    f(4) = 4 × f(3) = 4 × 3 × 2 × 1 × f(0) = 24, puisque le cas de base renvoie 1. 120 est f(5), 6 est f(3), et 10 additionnerait au lieu de multiplier.

  • Une preuve par récurrence se déroule en trois temps : l'…, l'…, puis la conclusion.

    Voir la réponse

    Une preuve par récurrence se déroule en trois temps : l'initialisation, l'hérédité, puis la conclusion.

    L'initialisation vérifie la propriété au premier rang, l'hérédité la fait passer de n à n + 1, la conclusion en déduit qu'elle est vraie pour tout n à partir de ce rang. Aucune des deux premières ne suffit seule.

  • Hérédité : de quoi s'agit-il ?

    Voir la réponse

    Étape qui prouve, pour un entier n quelconque, que si la propriété est vraie au rang n, alors elle est vraie au rang n + 1.

    On ne démontre pas la propriété au rang n, on la suppose : c'est l'hypothèse de récurrence. Ce qu'on démontre est l'implication P(n) ⟹ P(n + 1).

  • Pour prouver que tout entier n ≥ 2 est un produit de nombres premiers, on écrit n + 1 = a × b avec 2 ≤ a, b ≤ n. Quel raisonnement faut-il ?

    • Une récurrence simple, car l'hypothèse au seul rang n suffit à conclure
    • Une récurrence double, avec deux initialisations consécutives aux rangs 2 et 3
    • Aucune récurrence, car les nombres premiers se prouvent en testant chaque diviseur
    • Une récurrence forte, car a et b sont deux rangs quelconques ≤ n
    Voir la réponse

    Une récurrence forte, car a et b sont deux rangs quelconques ≤ n

    a et b peuvent être n'importe quels entiers entre 2 et n, pas seulement n : il faut la propriété à tous les rangs précédents, donc la récurrence forte. Dans le cas où n + 1 est premier, c'est directement un produit d'un seul facteur.

Réviser ce deck