Récursivité

In [ ]:
%pylab inline
%load_ext tutormagic
Populating the interactive namespace from numpy and matplotlib

Question

On considère le code ci-dessous :

def u(n):
    if v(n):
        res = n
    else:
        res = 0
    return res

def v(n):
    if n % 2 == 0:
        res = (u(n + 1) == 0)
    else:
        res = False
    return res

(a) Ce code est-il syntaxiquement correct ?

(b) Si oui, quel est le résultat du calcul u(6) ?

(c) Plus généralement, quel est le résultat du calcul u(n), si n est un entier naturel ?

Le code est syntaxiquement correct mais possède une singularité : le code de chacune des deux fonctions u et v comporte un appel à l'autre fonction. Il est légitime de s'interroger sur l'effet que ceci va produire lors de l'exécution. L'observation avec PythonTutor met en évidence le fait que le mécanisme de la pile d'appels fonctionne tout aussi bien dans cette situation. À un instant donné plusieurs instances d'une même fonction peuvent se retrouver dans la pile. Chacune de ces instances possède son propre contexte local.

Instrumentons le code en traçant les appels et les retours d'appel à l'aide des fonctions empile et depile :

In [ ]:
def u(n):
    empile("u", n)
    if v(n):
        res = n
    else:
        res = 0
    depile("u", res)
    return res
    
def v(n):
    empile("v", n)
    if n % 2 == 0:
        res = (u(n + 1) == 0)
    else:
        res = False
    depile("v", res)
    return res


def empile(nom, val):
    global compteur
    print("  " * compteur + "-->", nom, val)
    compteur = compteur + 1

def depile(nom, val):
    global compteur
    compteur = compteur - 1
    print("  " * compteur + "<--", nom, val)


compteur = 0
print(u(6))
--> u 6
  --> v 6
    --> u 7
      --> v 7
      <-- v False
    <-- u 0
  <-- v True
<-- u 6
6

À tout instant la variable globale compteur contient le nombre de contextes locaux présents dans la pile d'appels.

Remarque : En Python une fonction ne peut normalement pas modifier une variable globale telle que compteur. On a ici utilisé le mot-clé global pour contourner exceptionnellement cette inderdiction. Un bon programmeur s'interdit l'usage de ce mot-clé dans des programmes grandeur nature car il a le soucis d'écrire des fonctions bien isolées les unes des autres et de minimiser les effets de bords.

Combien vaut $u(n)$ ?

Nous n'avons pas encore répondu à la question : combien vaut $u(n)$ ? Ceci nécessite un raisonnement sur le code. En observant ce code on peut enchaîner les déductions suivantes :

  1. Si $n$ est impair, l'appel v(n) retourne False.

  2. Si $n$ est impair, l'appel u(n) retourne 0.

  3. Si $n$ est pair, $n+1$ est impair et donc, l'expression u(n + 1) == 0 est évaluée à True.

  4. Si $n$ est pair, l'appel v(n) retourne True.

  5. Si $n$ est pair, l'appel u(n) retourne n.

Remarquez que ce raisonnement démontre en particulier que la pile d'appels finit par se vider totalement et que l'on retourne au contexte global au bout d'un nombre fini d'opérations. Sachant que chacune des fonctions u et v peuvent s'appeler mutuellement, cela n'était pas garanti a priori.

Une fonction peut-elle s'appeler elle-même ?

Le mécanisme de la pile d'appels permet-il l'écriture de code tel que celui-ci :

In [ ]:
L = []

def callmyself(n):
    L.append(n)
    callmyself(n + 1)

callmyself(1)
print(L)
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-1-dd5f3ed7c33b> in <module>()
      5     callmyself(n + 1)
      6 
----> 7 callmyself(1)
      8 print(L)

<ipython-input-1-dd5f3ed7c33b> in callmyself(n)
      3 def callmyself(n):
      4     L.append(n)
----> 5     callmyself(n + 1)
      6 
      7 callmyself(1)

... last 1 frames repeated, from the frame below ...

<ipython-input-1-dd5f3ed7c33b> in callmyself(n)
      3 def callmyself(n):
      4     L.append(n)
----> 5     callmyself(n + 1)
      6 
      7 callmyself(1)

RecursionError: maximum recursion depth exceeded

La trace d'appels montre que l'interpréteur Python a exécuté le code. Il a donc considéré ce code comme syntaxiquement correct. Par contre, une exception s'est produite durant l'exécution : RecursionError. En observant attentivement cette trace d'appels, on remarque des points de suspensions qui laissent entendre que cette trace a été écourtée à l'affichage.

Que contient la liste L ?

In [ ]:
print(L)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 577, 578, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 594, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611, 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626, 627, 628, 629, 630, 631, 632, 633, 634, 635, 636, 637, 638, 639, 640, 641, 642, 643, 644, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659, 660, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736, 737, 738, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751, 752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 779, 780, 781, 782, 783, 784, 785, 786, 787, 788, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 804, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850, 851, 852, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871, 872, 873, 874, 875, 876, 877, 878, 879, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974]

Le mécanisme de la pile d'appels a fonctionné normalement :

  • L'appel callmyself(1) a créé un contexte local avec n = 1.
  • L'instruction L.append(n) a ajouté 1 dans la liste L.
  • L'instruction callmyself(n + 1) a créé un nouveau contexte avec n = 2.
  • L'instruction L.append(n) a ajouté 2 dans la liste L.
  • L'instruction callmyself(n + 1) a créé un nouveau contexte avec n = 3.
  • etc.

Le processus est clairement infini. Cependant la mémoire à la disposition de Python n'est pas infinie. La pile d'appels ne peut pas grossir indéfiniment. Lorsque la taille limite est atteinte, l'interpréteur Python lève l'exception RecursionError, ce qui met fin au programme.

Fonction récursive

Question I : Peut-on écrire des fonctions Python qui s'appellent elles-mêmes sans provoquer de RecursionError ?

Question II : Si oui, la possibilité d'écrire des fonctions python qui s'appellent elles-mêmes a-t-elle un intérêt ou bien est-ce purement anecdotique ?

Étudions par exemple le code ci-dessous :

In [ ]:
%%tutor -t
def tcaf(n):
    if n == 0:
        return 1
    else:
        return n * tcaf(n - 1)

Quel résultat obtient-on en exécutant tcaf(4) ?

In [ ]:
tcaf(4)
Out[ ]:
24

Utilisons Pythontutor pour observer l'exécution pas à pas. Ici, les contextes locaux ne s'empilent pas indéfiniment. L'appel tcaf(0) retourne immédiatement 1 sans effectuer d'appel supplémentaire. On observe alors que les contextes sont dépilés un à un en retournant les valeurs calculées. Remarquez qu'il doit exister au moins un cas où la fonction récursive ne s'appelle pas elle-même. Sinon, il est clair que la pile d'appels grossit indéfiniment jusqu'à aboutir à l'exception RecursionError.

Question : Que calcule tcaf(n) ?

Réponse : L'appel tcaf(n) retourne la factorielle de n.

La factorielle d'un entier naturel $n$ est définie par :

$$\begin{cases} 1 & \text{si }n = 0\\ n\times (n - 1)! &\text{si }n\gt 0. \end{cases}$$

La factorielle d'un entier naturel $n$ est définie par :

def factorial(n):
    """Retourne la factorielle de n
    """
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Les deux définitions ci-dessus ne diffèrent que superficiellement. La première utilise le langage mathématique habituel. La seconde est écrite avec la syntaxe du langage Python.

Il est intéressant de comparer ce code python avec celui que l'on peut produire à l'aide d'une boucle.

Bref retour sur la structure itérative

Si l'on pense de façon itérative, on visualise $n!$ de cette façon :

$$1\times 2\times 3\times 4\times\dots\times n$$

On calcule pas à pas les produits partiels en utilisant une boucle :

In [ ]:
def factorial(n):
    """Retourne la factorielle de n
    """
    k = n
    prod = 1
    while k > 1:
        # Propriété : n! = prod * k!
        prod = prod * k
        k = k - 1
    return prod

factorial(5)
Out[ ]:
120

Cette version itérative est plus technique. Le code itératif entre dans les détails du comment calculer la factorielle. Il est par ailleurs moins évident de se convaincre que l'algorithme fait bien ce qu'il est censé faire. Ici, pour s'en convaincre, on peut raisonner de la façon suivante :

  1. Au début de chaque itération on a $n! = prod\times k!$ :
    • C'est vrai lors de la première itération $prod=1$ et $k=n$.
    • Si cela est vrai lors d'une itération, c'est encore vrai lors de l'itération suivante car $n! = prod\times k! = (prod\times k)\times (k-1)!$
  2. L'entier $k$ décroit strictement. La condition d'arrêt de la boucle sera donc satisfaite en un nombre fini d'itérations.
  3. En sortie de boucle on a $n! = prod\times k!$ et $k=0$, et par conséquent $prod=n!$. La fonction retourne donc bien la factorielle de $n$.

L'expression $n! = prod\times k!$ est appelé un invariant de boucle. Le concept d'invariant de boucle est un outil pour concevoir une boucle de façon méthodique et avoir la certitude qu'elle produit bien un résultat correct.

La pensée récursive

Une fonction qui s'appelle elle-même est nommée fonction récursive. Cette possibilité offerte par le langage Python d'écrire des fonctions récursives n'est pas anecdotique. Elle ouvre de nouvelles façons de penser et de concevoir la solution des problèmes algorithmiques.

Par opposition à la programmation itérative, le style récursif met en avant la spécification externe de la fonction, c'est-à-dire sa définition au sens de définition mathématique. Les détails du calcul sont gérés par l'interpréteur lui-même à travers le mécanisme de la pile d'appels.

À ce stade, ouvrons une petite parenthèse. Que l'on pense récursivement ou non, résoudre un problème consiste à chercher à le réduire.

Réduction d'un problème

Pour résoudre un problème algorithmique une bonne démarche est de chercher à le décomposer en sous-problèmes plus simples. La solution de chaque sous-problème pourra alors se traduire par une fonction python spécifique. L'exemple du tri par sélection que nous avons vu lors du dernier cours en est une illustration.

In [ ]:
def tri(L):
    """ Tri la liste L par ordre croissant."""
    n = len(L)
    for i in range(n - 1):
        j = selectMin(L, i)
        L[i], L[j] = L[j], L[i]

Le code ci-dessus réduit le problème du tri au problème de savoir trouver l'indice k >= i où se trouve la plus petite valeur de L[i:].

In [ ]:
def selectMin(L, i):
    """ Retourne l'indice k >= i contenant 
        la plus petite valeur de L[i:].
    """
    n = len(L)
    k = i
    for j in range(i + 1, n):
        k = indexMin(L, k, j)
    return k

Ce second problème est lui-même réduit au problème de trouver entre deux indices de L, celui qui contient la plus petite valeur.

In [ ]:
def indexMin(L, k, j):
    """ Retourne l'indice k ou j contenant 
        la plus petite valeur.
    """
    if L[j] < L[k]:
        return j
    else:
        return k

Dans le cas d'une recherche d'une solution récursive on tente de réduire le problème à un problème identique mais de taille plus petite. Si la taille est suffisamment petite, on résout le problème directement ce qui permet de garantir que le processus de réduction ne se poursuit pas indéfiniment. Ce que l'on entend par taille dépend spécifiquement du problème à résoudre.

Illustrons cette idée par des exemples.

Problème I

Recouvrir l'échiquier écorné ci-dessous avec des copies de la pièce bleue.

Échiquier écorné

Comme nous l'avons dit, il faut chercher à réduire le problème à un problème de taille plus petite. Mais qu'entend-on par taille ici ? Penser récursivement conduit à résoudre non pas un seul problème mais une famille de problèmes identiques de tailles variables.

Première tentative de réduction :

Première tentative de réduction

Le problème est réduit ici à quatre problèmes. Mais trois d'entre eux ne sont pas identiques au problème initial.

Seconde tentative de réduction :

Seconde tentative de réduction

Le problème initial $P$ est posé pour un échiquier de $8\times 8$ cases. Nous introduisons un paramètre $n$ et nous définissons le problème $P(n)$ consistant à paver un échiquier écorné de côté $2^n$. Le schéma ci-dessus montre que toute solution du problème $P(n-1)$ fournit une solution au problème $P(n)$. Nous avons ainsi réduit le problème $P(n)$ au problème $P(n-1)$.

Étant donné que le problème $P(1)$ a une solution évidente, nous obtenons ainsi la preuve que $P(n)$ a une solution pour tout $n\geq 1$. Nous avons d'ailleurs plus qu'une preuve : nous avons un algorithme de construction d'une solution.

Problème II

Écrire une fonction récursive pgcd(a, b) qui retourne le pgcd de deux entiers naturels $a$ et $b$.

Il s'agit de réduire ce problème à un problème identique de taille plus petite, autrement dit au calcul du pgcd de deux autres entiers. Mais lesquels ? Et quelle est la taille du problème ici ?

Le mathématicien Euclide vient à notre aide :

  • Il existe $q\in\mathbf{Z}$ tel que $a = qb + (a\bmod b)$

  • $d$ divise $a$ et $b$ si et seulement si $d$ divise $b$ et $d$ divise $(a\bmod b)$.

  • $\text{pgcd}(a,\, b) = \text{pgcd}(b,\, a\bmod b)$

  • $\text{pgcd}(a,\, 0) = a$.

Nous avons ainsi notre algorithme récursif :

$$\begin{cases} \text{pgcd}(a,\, 0)\\ \text{pgcd}(a,\, b) = \text{pgcd}(b,\, a\bmod b) \end{cases}$$
In [ ]:
def pgcd(a, b):
    "Retourne le pgcd de a et de b"
    if b == 0:
        return a
    else:
        return pgcd(b, a % b)
    
pgcd(80, 12)
Out[ ]:
4

Attention : Les affirmations énoncées ci-dessus ne garantissent pas complètement que le code de la fonction pgcd est correct. En effet, il est également exact que $\text{pgcd}(a,\, b) = \text{pgcd}(b,\, b + a\bmod b)$. Cependant, l'exécution du code ci-dessous échoue :

In [ ]:
def pgcd(a, b):
    "Retourne le pgcd de a et de b"
    if b == 0:
        return a
    else:
        return pgcd(b, b + a % b)
    
pgcd(80, 12)
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-15-857de7a3d595> in <module>()
      6         return euclide(b, b + a % b)
      7 
----> 8 euclide(80, 12)

<ipython-input-15-857de7a3d595> in euclide(a, b)
      4         return a
      5     else:
----> 6         return euclide(b, b + a % b)
      7 
      8 euclide(80, 12)

... last 1 frames repeated, from the frame below ...

<ipython-input-15-857de7a3d595> in euclide(a, b)
      4         return a
      5     else:
----> 6         return euclide(b, b + a % b)
      7 
      8 euclide(80, 12)

RecursionError: maximum recursion depth exceeded in comparison

Pour justifier que la fonction pgcd est correcte il faut montrer que les appels récursifs se terminent. Comme pour les boucles, l'argument usuel est de mettre en évidence une quantité entière qui décroit strictement. Dans le cas présent, on peut utiliser le fait que $0\leq (a\bmod b) \lt b$.

Montrons par récurrence forte sur $b$ que pgcd(a, b) se termine et retourne le pgcd de $a$ et de $b$.

  • Si $b=0$ la fonction se termine en retournant $a$ ce qui est bien le pgcd de $a$ et de 0.

  • Si $b\gt 0$, pgcd(a, b) fait un appel à pgcd(b, a % b). Or $(a\bmod b) \lt b$. Par hypothèse de récurrence, pgcd(b, a % b) se termine et retourne le pgcd de $b$ et de $a\bmod b$. La fonction retourne alors elle-même cette valeur qui est bien égale au pgcd de $a$ et de $b$.

Problème III - Les tours d'Hanoï

Les tours de Hanoï sont un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de départ à une tour d'arrivée en passant par une tour intermédiaire, et ceci en un minimum de coups, tout en respectant les règles suivantes :

  • on ne peut déplacer plus d'un disque à la fois ;
  • on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

On peut vérifier que les instructions suivantes permettent de déplacer quatre disques de la tour $A$ (à gauche) vers la tour $C$ (à droite) en utilisant la tour $B$ (au centre) comme intermédiaire :

A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C

Question

Écrire une fonction python hanoi qui imprime la suite minimale d'instructions qui permet de résoudre le problème.

Il est ici naturel de choisir le nombre $n$ de disques comme taille du problème. La question est alors :

La connaissance d'une solution pour le problème de taille $n-1$ permet-elle de construire une solution pour le problème de taille $n$ ?

Un peu de réflexion permet de répondre oui à cette question. Supposons que nous disposions d'une méthode pour déplacer $n-1$ disques d'une tour vers une autre, en utilisant une troisième tour comme intermédaire. Nous pouvons alors utiliser cette méthode comme méthode auxilliaire pour déplacer les $n$ disques de $A$ vers $C$ en utilisant $B$ comme intermédiaire :

Déplacer n - 1 disques de A vers B en utilisant C
Déplacer le disque restant de A vers C
Déplacer les n - 1 disques de B vers C en utilisant A

Cette méthode récursive peut se traduire en Python de la façon suivante :

In [ ]:
def hanoi(n, left, right, center):
    """ Imprime les instructions pour déplacer n disques
        de la tour left vers la tour right 
        en utilisant la tour center comme intermédiaire.
    """
    if n == 1:
        print(left, "-->", right)
    else:
        hanoi(n - 1, left, center, right)
        print(left, "-->", right)
        hanoi(n - 1, center, right, left)

hanoi(4, "A", "C", "B")
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C

Exercices

Question 1

Écrire une fonction récursive somme_cubes qui calcule la somme cubes des $n$ premiers entiers naturels non nuls.

In [ ]:
 

Question 2

Écrire une fonction récursive maxi(L) qui retourne l'élément maximal de la liste L.

Bien entendu, la fonction max de la biliothèque standard n'est pas autorisée.

In [ ]:
 

Question 3

La racine digitale d'un entier naturel $n$ est calculée de la manière suivante. Commencez par additionner tous les chiffres de $n$. Les chiffres du résultat de cette somme sont ensuite ajouté et le processus continue jusqu'à ce que l'on obtienne un résultat à un seul chiffre. Par exemple, la racine digitale de 2019 est 3 car $2+0+1+9=12$ et $1+2=3$.

Écrire une fonction récursive racine_digitale(n) qui retourne la racine digitale de $n$.

In [ ]:
 

Question 4

Écrire une fonction récursive solve telle que solve(f, a, b) donne une solution approchée de l'équation $f(x)=0$ sur l'intervalle $[a, b]$.

La fonction suppose que $f$ est continue et que $f(a)$ et $f(b)$ sont de signes distincts.

In [ ]: