La récursivité

Exemple introductif⚓︎

On veut écrire une fonction qui produit l'affichage de triangles de n lignes, la première ligne contenant un *, la seconde deux * et ainsi de suite. Par exemple pour n=4, la fonction doit afficher :

Text Only
1 2 3 4	`* * ****`

Une des possibilités est d'utiliser une boucle, on dit que la fonction est itérative :

Python
def triangle(n):
    for i in range(1,n+1):
        print("*"*i)

En observant la représentation ci-dessous, on constate aussi qu'il est possible de définir un triangle de 5 lignes par rappport à un triangle de 4 lignes, et plus généralement un triangle de n lignes par rapport à un triangle de n-1 lignes :

triangle_recursif

En effet, construire un triangle de n lignes c'est :

construire un triangle de n-1 lignes
ajouter une ligne de n étoiles

on vient de donner une méthode de construction récursive, qui doit se compléter en précisant qu'elle n'est valable que pour n>0. Cette définition trouve se traduit en python par :

Python
def triangle_recursif(n):
    if n>0:
        triangle_recursif(n-1)
        print('*'*n)

Définition⚓︎

A retenir

Une fonction est dite récursive lorsqu'elle fait appel à elle-même. Par conséquent,

une fonction récursive permet, comme une boucle, de répéter des instructions puisque le bloc d'exécution de la fonction est rappelé (mais avec des paramètres différents).
une même fonction peut donc se programmer de façon itérative (avec des boucles) ou de façon récursive (en s'appelant elle-même).
une fonction récursive doit toujours contenir au moins une condition d'arrêt (sinon elle s'appellera elle-même à l'infini)

Exemples corrigés⚓︎

Factorielle d'un entier⚓︎

La factorielle d'un entier est le produit de cet entier par tous ceux qui le précèdent (excepté 0). Cette fonction a déjà été programmé de façon itérative mais elle s'exprime aussi par rapport à elle même et donc peut être programmé de façon récursive, en effet :
$n! = n \times \underline{(n-1)\times \dots \times 1}$ et puisque la partie soulignée vaut $(n-1)!$ :
$n! = n \times (n-1)!$
Cette écriture se traduit directement en Python par :

Python
def factorielle(n):
    if n==0:
        return 1
    else:
        return n*factorielle(n-1)

Il faut bien comprendre que par exemple pour calculer factorielle(4) python procédera de la façon suivante :

calculer factorielle(3) et le multiplier par 4
calculer factorielle(2) et le multiplier par 3
calculer factorielle(1) et le multiplier par 2
calculer factorielle(0) et le multiplier par 1
comme la condition d'arrêt donc factorielle(0)=1, on peut remonter dans le calcul et obtenir 24

Somme des éléments d'une liste⚓︎

La somme des élements d'une liste $l = [l[0],\dots l[1]]$ peut s'exprimer ainsi :

si la liste est vide c'est zéro (condition d'arrêt)
sinon c'est le premier élément de la liste plus la somme de la liste à partir du second élément

c'est donc une définition récursive puisque nous avons exprimé la somme d'une liste à partir de la somme d'une (autre) liste. En python, il suffit de pouvoir exprimer la liste à partir du second élement à l'aide du tranche et on peut écrire :

Python
def somme(l):
    if l==[]:
        return 0
    else:
        return l[0] + somme(l[1:])

Retourner une chaine de caractère⚓︎

Note

En cas de besoin, on conseille de revoir les tranches avant d'aborder cet exemple.

On veut écrire une fonctions récursive qui renvoie la chaine de caractère donnée en argument à l'envers. Par exemple envers("Python") doit renvoyer "nohtyP". Comme précédemment, afin d'écrire une version récursive de cette fonction, il faut exprimer l'envers d'une chaine par rapport à l'envers d'une autre chaine (plus courte). On peut remarquer que pour écrire une chaine à l'envers, il suffit d'écrire son dernier caractère puis l'envers du reste de la chaine ce qui se traduit en Python par :

Python
def envers(chaine):
    if chaine=="":
        return ""
    else:
        return chaine[-1] + envers(chaine[0:-1])

Exercices⚓︎

Compléter le code de la fonction occurrences, qui prend en argument une liste d'entiers l et un entier n et renvoie le nombre d'apparitions de n dans l.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013oP;f 8lkg5:+,Fbry2a1éh3tvwT=u6e[(Sàn9]_s-c)7im/4p0d050Z0F0y0t0T0h0O0f0Q0h0t0O0O0C010y0T0X010406050O0D0U0U0t0q0r040I0b0h0D0@0b0K050V0~1012140|0X04051k1d1n0V1k0|0Z0T0z0,0.0:0=0.0K0j0D0t0j0F0P0X0r0y0w1b0f0w0T0j0w0h1P0w0y0`050%0p0h0F1w0/0;011O1Q1S1Q0y1Y1!1W0y0q1l1K0,170O0X0t0K0=0s011$1y010e0)0F0K0t0U0F1W1{1}221(251!282a0`0a0f0c0q0b0X0b0O0T1a0K0f0#1_0q0q0F0Q2v1d2d0K1l0V1K2I1=1@1?1X0Z2f1z0T0K272s1W1t1v0-1%2S2U0K0b2Y1W0X2B1l2G2I2/0}1|2w2!232(0q110h1W0t1N2B0e0=030N0N0Q2)0F1S2%0b0P0E0P0u0`0u1d0t2:2?0{2=2e2^1(2`2|2~300F32013436383a2V3d0P20040s3j3l1}3n2G2R013s0t2}1l2 0w313335370#3C2(3E0x0`0x3J2F3m0|3N3q0=3Q3S053U3W3y3Y3B2T3D3e0W0`0W3+1e3-3o2@1x3r0b2{3R3u3V3w3X3A3!3}3$3e0k0`0k432/3.2?3O3=4d3_3z3Z394j3c3e0E0`0E4p453/483;4a3t3T3v3x4x3|3b3E0S0`0S4G3L4r3p4J3P4L4c4N4e4P3{4i4S3e0g0`0g4X2H4Z472#4$4b3?3^4f3`4h4z4.0P0L0`0L4?2I2,0F2I2Y2L0Z1@2Q3:014y2X1u1l5a2.3m3,3L054y5p2e0T0Z0=352G3E3g4N5x5z513#4B3f212j0F5G4y5I5C1W0V3k463O0i0`0#0e5r2H5V5i0A0`0f5#5v4_2_0e0`0b0Q0Q0D2A270Q0F0O5,5%4#0_040H5~4I4`0K0`0h644s5i610l5,5+652_0p680T0O0y6a4!4`610n6f5 660`1c445s6h1(6d6o5.3r6j042T6n6y5$6A0=610R6t6M010b0`0P020j0y0d6Q6b4#0K6G6I6D3O6C6K3n6-5V5F015A2?3E3G3@0f6;4,523~3F5L295N6=5H4A6^5S3k0f7a6g6#4`5X6H5!6-7c6p2_686!7k1(6T040C0C7n6E6N0`0G0M6e6-0|6/3N6|0N5B3e3(5E5y745P767I712a5O4R6 7J3J7b7X7j7v017f2B0y5^6x2/7Z3O0U0T0`0Y5,7C2;7E7L6?1}3E407K7S4-6 400f5M7 6~4k0P7}3J7?5q7^5G7H0P4m7~7M7T874m8372855Q4l78047X6u230Q5D030f2t2(0K0n0f390O1#2T19260f0t0z2C0f1!0f7%7)0f0J8Q2 1,2U0f2,0v0Q0v0#0K0y0F7=6*7F8f4D8i6}8q3d7Q738@7O8_2I797b8v3r0`5a8H0K5{0N257*3m7,5i7q7t7i923;6(8+6*6c0`637D7d7l04699q7o7w040G9m4#7q0P9A4`7.3h9E23610M7u3O9f9g7+9i3P6w9I6B0`6P9h6R8x0`8z0B0q0D1#5|0y8S0F0U0X0.8(8#120f0u8E0o3R8H9?0q0f7;7B8/7_7G6@3e4U8?75534U8n7R8j8087a87W916R7$0$7)9M5i6704955`0F992Tap9B0`0may6v045=5@5_975|9U9x9p7@9r939taK01610G7AaN9w6S6UaR9G043i9v7!9K6s9YaO3;9Ta(6+9W8.a:8:a60P4:a97N534:ad8{aa6 a{8aa38ea_55a|8k5J55b08p8}b93+al0`1%0F0q6J9Q6RaraF5^2BaI5}a:9n629zbx4#a#a%aWa)0`a+bpa-01a#3*bB6qbHaC23bMaRa*bR1(bTbO9Ja=a,aX9ObW0=a#3Ia26/0V5u1o2-1d5d1d0y5fb^2O2J0t1Z5bb?5m7C0#0%0)0O04.
Dans le bac à sable, écrire une version récursive des fonctions suivantes :
1. Fonction puissance, qui prend en argument un nombre $x$ et un entier $n$ (positif) et renvoie $x^n$.
2. Fonction palindrome, qui prend en argument une chaine de caractère et qui renvoie True lorsque cette chaine est un palindrome, False sinon.
3. Fonction maximum, qui prend en argument une liste d'entiers et renvoie le maximum des éléments de cette liste.
Modifier la fonction triangle_recursif de l'exemple introductif afin d'afficher le même triangle mais "pointe vers le bas".
Complète le code suivant qui retourne le PGCD de a et b

Note

Si $a >= b$:

l'algorithme d'Euclide nous donne l'égalité : $pgcd(a,b) = pgcd(b, a - b)$.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013oP;f 8lkg5:,bry2a1éh3tvw=u6e(Sn_s-c)7iêm/4p0d050T0C0w0r0M0h0H0f0J0h0r0H0H0z010w0M0R010406050H0A0O0O0r0o0p040E0b0h0A0.0b0F050P0^0`0|0~0?0R04051e171h0P1e0?0T0M0x0$0(0*0,0(0F0j0A0r0j0C0I0R0p0w0u150f0u0M0j0u0h1J0u0w0;050X0n0h0C1q0)0+011I1K1M1K0w1S1U1Q0w0o1f1E0$110H0R0r0F0,0q011W1s010e0Z0C0F0r0O0C1Q1=1@1|1Y1 1U22240;0a0f0c0o0b0R0b0H0M140F0f0V1:0o0o0C0J2p17270F1f0P1E2C1,1.1-1R0T291t0M0F212m1Q1n1p0%1X2M2O0F0b2S1Q0R2v1f2A2C2)0@1?2q2U1}2Y0o0{0h1Q0r1H2v0e0,030G0G0J2Z0C1M2X0b0I0L0I0s0;0s170r2*2-0=2,282/1Y2;2?2^2`0C2|012~3032342P370I1`040q3d3f1@3h2A2L013m0r2@1f2_0u2{2}2 310V3w2Y3y0v0;0v3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380Q0;0Q3#183%3i2.1r3l0b2=3L3o3P3q3R3u3U3@3W380k0;0k3}2)3(2-3I3,473:3t3T334d36380B0;0B4j3 3)423+443n3N3p3r4r3?353y0L0;0L4A3F4l3j4D3J4F464H484J3=4c4M380g0;0g4R2B1i2%172S2F0T1.2K3*014s2R1o1f2$0C2(3g3$3F054s52280M0T0,2 2A3y3a4H5a5c4b4t4(391{2d0C5j4s3V4v5n2C3e403I0i0;0V0e544.4C2V010y0;0f5E58415H0F0e0;0R0j0J0T5M5y4`0:040D5X5G2:0;0r5%4m5Z0;0m5,4U5P0;0n5;5O1}5!0K0l5M0?3~553H5i015d2-3y3A3.0f644$5l3^3z5o235q655k5t681Q0P3e0f6r5L5(1Y5A040M5D612B6t5-4V0F5@5M6C5=1}0b0;0z0z6H5Y4V0O0M0;0S5_3I5!5~6A3h6!5y6c0G5e383Y5h5b6k5s4u3X6h245r4L6f6,3D6s6}6I5`6v0;2v0w0A0o166!6 4n5*6P6u0,0J5g030$0)2r1V0n0)0C0m1:0F1n2p2r000|0o0N0w5 6W6(6*0I3`6-6^4%6f3`0f5p7H6e4e7E6o6q6s6Q5H6w6y7c6D5?045+787U6K0;020h0w0d7Y6J3l6G6$7d016Y7A7?4m7C674f3o6(6:5m4g7L6i7N6m7 5w046~7T7@6w7375772)794`6F045T5V6W5.5#8q6E7=2+7@5!5:7{7:3+7b8A700,5|7/8F4{7g2h0b750f0j0|0V0o0f2_020j7-0z0f0n7p210f0R0C2=131@0w8U0f0W8!7`8w7|6.661@3y4x7G6/6_7P4x856@8 7I917R8b8d7Z1}8f0W8h8I7a8n5U5W8E6X0;5$9l8l8v538x5/9g9q7#9v4V6L040I9y7!5^9p4V8H7%7@7f0;7h2_310O0R0h0t0w8*8?9s8^5j7D4O8~6d88376?6j9%6;389#3D608@598_6)7~0I4*9$6l9-9`9*879~9{3#8e5*0*8*7z9J9b7;9i8p9G5H5!9o9=8J6S4y6Vaf5{9uaa8B01al3B3|ao1Y9I8j7(1Y9A6N9D1}au0s3C6!9;530P574/514;4~170w4@aT2I2D0r1TaQ0P4=600V0X0Z0H04.
Écrire, dans le bac à sable, une fonction cbinomial doublement récursive qui calcule les coefficients du binomes selon la relation :

\[ \binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p} \]
La suite de Fibonacci est définie par la relation de récurrence suivante :

\[ Fibo(0) = 0,\quad Fibo(1) = 1 \]

Et pour tout entier $n > 1$ :

\[ Fibo(n) = Fibo(n-1) + Fibo(n-2) \]

Complète le code suivant qui retourne le terme de Fibonacci : Fibo(n)

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013oPf 8lkg5:+F,bry2a1}hA3tvw=u6{e(ESn9x_s-c)7im/4p0d050Y0F0y0s0S0g0N0e0P0g0s0N0N0B010y0S0W010406050N0C0T0T0s0p0q040I0b0g0C0?0b0J050U0}0 11130{0W04051j1c1m0U1j0{0Y0S0z0+0-0/0;0-0J0i0C0s0i0F0O0W0q0y0v1a0e0v0S0i0v0g1O0v0y0_050$0o0g0F1v0.0:011N1P1R1P0y1X1Z1V0y0p1k1J0+160N0W0s0J0;0r011#1x010d0(0F0J0s0T0F1V1`1|211%241Z27290_0a0e0c0p0b0W0b0N0S190J0e0!1^0p0p0F0P2u1c2c0J1k0U1J2H1;1?1=1W0Y2e1y0S0J262r1V1s1u0,1$2R2T0J0b2X1V0W2A1k2F2H2.0|1{2v2Z222%0p100g1V0s1M2A0d0;030M0M0P2(0F1R2$0b0O0f0O0t0_0e0t1c0s2/2=0`2;2d2@1%2_2{2}2 0F3101333537392U3c0O1 040e0r3j3l1|3n2F2Q013s0s2|1k2~0v303234360!3C2%3E0x3g0x3K2E3m0{3O3q0;3R3T053V3X3y3Z3B2S3D3d0V3g0V3,1d3.3o2?1w3r0b2`3S3u3W3w3Y3A3#3~3%3d0j3g0j442.3/2=3P3?4e3`3z3!384k3b3d0D3g0D4q463:493=4b3t3U3v3x4y3}3a3E0R3g0R4H3M4s3p4K3Q4M4d4O4f4Q3|4j4T3d0f3g0f4Y2G4!482!4%4c3@3_4g3{4i4A4/0O0K3g0K4@3N4t3;4|4N3^4P4h4z3$4C3e0X0_0t0X594_4u4(4~5g515i4B3E0t3f045A591n2,1c2X2K0Y1?2P5c4z2W1t1k2+0F2-3m3-3M054z5U2d0S0Y0;342F5z3u5$5(525j5+0e2i0F5.5x545B3,4J4{0h0_0!0d5W2G473P0A3g635!4`2^0d0_240o0b69655c0^040G6i5}2^0_1b455X6p1%6l0Q0k690{6t643O5-015)2=3E3G5f6F4-533 3F205?5^4S6P6K0U3k0e6Z0e6j4$5 040S626C3H6$4{0J6r696#6v0;0b0_0B0B6=6.220T0S0_5p6,6~6w0_6z6,6B2:6E5%6G0M5*3d3)4O6M5/5y7h6R285@7e5_6P7i3K6!7w6?5b6%0_2A0y0C0p6s2.7y4#4{70726A6o4t7k7g0O417j7d6N5:407o296T4.6P7T7v6!750;6(4A6+7H7+3Q6;6,7I6b1%6_046{6}6@017L5C7O7J226l784r832v7Q6I4m5,7V7l544n5=7p7#6O4l0O4n2H6Y7x6Z7;6(7C7E7G3m7^3P813i79890e8b1|3E4E7U8l7X0O4E8j7!7r6U8n8K7)8t7 7-0)0F8F6k777N747c5.7R4V8L8S7$8n4V8Q7q7W7m0O8.8W7x8u7B0#8x7~7z6/6e0S6g8$4$6l6n8*946q048y3M8A5c7{0O93841%8C994{6x9n7_6^0_0l9u4u96989d9o0;9b9r9f9h2G9j4$9l9z5c813J9D9v019t8E9S8G8f7R4;8/8_544;8@8M8`9#3K7a5V8+7e7R569$8g6P569*8:8m5k9@5|9e1%0P5B030e0H0L0F0T0W1Z2w00180(0S0N0s2D9W7b7P9Z8c5l8e9+5`5m9|9%6P5o1V6X6a9A9g9O9M6`aF7K715C73889X8H0J5z5{2~7k7s8n5A7Z8^9_aW5{aB7;0J0o0_2+2S0y9H766ma/0;aj6ea=010N3G010m970b9can9Ea`aK0Ea_6:aE9X5c2s0_0ua_a{0_0Q0e0;a_6l0naI9f6f6hba9a0_b19:a23=7?b29T6x0Q6=9L4{a40_a60w0d240P0v1!0m0G5obi0B0e0j4pam5V0U5Z5F5T5H5Q1c0y5Kb*2N2I0s1Yb%0U5I6B0!0$0(0N04.
Nombre de chemins dans une grille