La récursivité

Considérons le programme suivant :

Python
def fctA():
    print ("Début fonction fctA")
    i=0
    while i<5:
        print(f"fctA {i}")
        i = i + 1
    print ("Fin fonction fctA")

def fctB():
    print ("Début fonction fctB")
    i=0
    while i<5:
        if i==3:
            fctA()
            print("Retour à la fonction fctB")
        print(f"fctB {i}")
        i = i + 1
    print ("Fin fonction fctB")

fctB()

l'exécution de ce programme donne le résultat suivant :

Text Only

Début fonction fctB
fctB 0
fctB 1
fctB 2
Début fonction fctA
fctA 0
fctA 1
fctA 2
fctA 3
fctA 4
Fin fonction fctA
Retour à la fonction fctB
fctB 3
fctB 4
Fin fonction fctB

Dans l'exemple ci-dessus, nous avons une fonction (fctB) qui appelle une autre fonction (fctA). La principale chose à retenir de cet exemple est que l'exécution de fctB est interrompue pendant l'exécution de fctA. Une fois l'exécution de fctA terminée, l'exécution de fctB reprendra là où elle avait été interrompue.

Pour gérer ces fonctions qui appellent d'autres fonctions, le système utilise une "pile d'exécution". Une pile d'exécution permet d'enregistrer des informations sur les fonctions en cours d'exécution dans un programme. On parle de pile, car les exécutions successives "s'empilent" les unes sur les autres. Si nous nous intéressons à la pile d'exécution du programme étudié ci-dessus, nous obtenons le schéma suivant :

Nous pouvons "découper" l'exécution de ce programme en 3 parties :

la fonction fctB s'exécute jusqu'à l'appel de la fonction fctA
l'exécution de la fctB est mise en "pause" pendant l'exécution de la fonction fctA
une fois que l'exécution de fctA est terminée, on termine l'exécution de la fonction fctB

Il est important de bien comprendre que la fonction située au sommet de la pile d'exécution est en cours d'exécution. Toutes les fonctions situées "en dessous" sont mises en pause jusqu'au moment où elles se retrouveront au sommet de la pile. Quand une fonction termine son exécution, elle est automatiquement retirée du sommet de la pile (on dit que la fonction est dépilée).

La pile d'exécution permet de retenir la prochaine instruction à exécuter au moment où une fonction sera sortie de son ""état de pause" (qu'elle se retrouvera au sommet de la pile d'exécution) :

Évidemment l'explication donnée ci-dessus est quelque peu simpliste : c'est l'adresse mémoire de la prochaine instruction machine à exécuter qui est conservée dans la pile d'exécution

Dans l'exemple ci-dessus, on retrouve une variable i dans les deux fonctions : fctA et fctB. La variable i présente dans la fonction fctA n'a rien à voir avec la variable i présente dans la fonction fctB (elles portent le même nom, mais elles représentent 2 adresses mémoires différentes). Il est très important de bien comprendre que les variables créées dans une fonction ne "sortent" pas de la fonction : chaque fonction possède sa propre liste de variable, comme déjà dit ci-dessus la variable i de la fonction fctB est différente de la variable i de la fonction fctA.

La pile d'exécution conserve une "trace" des valeurs des variables lorsqu'une autre fonction est exécutée. Par exemple la valeur de i (fctB) est conservée au moment de l'exécution de fctA. Quand l'exécution de fctA se termine est que l'exécution de fctB "reprend", la valeur référencée par i (fctB) a été "conservée" (voilà pourquoi on reprend l'exécution de fctB avec un "fctB 3").

Une fonction peut s'appeler elle-même, on parle alors de fonction récursive.

Considérons de programme suivant :

Python
def fctA():
    print ("Hello")
    fctA()
fctA()

Si nous exécutons ce programme, nous allons obtenir une erreur :

Text Only
1	`RecursionError: maximum recursion depth exceeded while calling a Python object`

Dans le cas où une fonction s'appelle elle-même (fonction récursive), on retrouve le même système de pile d'exécution. Dans l'exemple traité ci-dessus, les appels s'enchainent sans rien pour mettre un terme à cet enchainement, la taille de la pile d'exécution augmente sans cesse (aucune fonction ne termine son exécution, nous n'avons pas de "dépilement" juste des "empilements"). Le système interrompt le programme en générant une erreur quand la pile d'exécution dépasse une certaine taille.

Quand on écrit une fonction récursive, il est donc nécessaire de bien penser à mettre en place une structure qui à un moment ou à un autre mettra fin à ces appels récursifs.

Dans le cas de fonctions récursives, il est, comme pour n'importe quelle fonction, possible d'utiliser des paramètres :

Soit le programme suivant :

Python
def fonct(n):
    if n>0:
        fonct(n-1)
    print(n)

fonct(3)

Analysons en détail le fonctionnement de ce programme :

1er appel de la fonction fonct avec le paramètre n = 3 ; n > 0 donc appel de la fonction fonct avec le paramètre n = 2
2e appel de la fonction fonct avec le paramètre n = 2 ; n > 0 donc appel de la fonction fonct avec le paramètre n = 1
3e appel de la fonction fonct avec le paramètre n = 1 ; n > 0 donc appel de la fonction fonct avec le paramètre n = 0
4e appel de la fonction fonct avec le paramètre n = 0 ; n = 0 donc on exécute l'instruction print(n) => affichage : 0
on "dépile" (3e appel, n = 1) : on exécute l'instruction print(n) => affichage : 1
on "dépile" (2e appel, n = 2) : on exécute l'instruction print(n) => affichage : 2
on "dépile" (1er appel, n = 3) : on exécute l'instruction print(n) => affichage : 3

Voici un schéma expliquant le processus en termes de pile d'exécution :

Il ne faut jamais perdre de vu qu'à chaque nouvel appel de la fonction fonct le paramètre n est différent.

Nous allons étudier le calcul de la factorielle grâce à une fonction récursive. D'après Wikipédia : "En mathématiques, la factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n". Par exemple : la factorielle de 3 est : 3 x 2 x 1 = 6 ; la factorielle de 4 est 4 x 3 x 2 x 1 = 24 ; la factorielle de 5 est 5 x 4 x 3 x 2 x 1 = 120 ...

Si on note la factorielle de n par n!, on a :

0! = 1 (par définition
Pour tout entier n > 0, n! = n x (n – 1)!

Nous allons utiliser cette définition de la factorielle pour définir notre fonction récursive (nous allons utiliser le fait que la factorielle de n dépend de la factorielle de n-1 et que 0! = 1)

Analysons le programme suivant :

Python
def fact(n) :
    if n > 0 :
        return n*fact(n-1)
    else :
        return 1

Comme vous pouvez le constater, la fonction fact est structurée de la même manière que la définition mathématique vu ci-dessus :

dans le cas où n = 0 la fonction renvoie 1 (0! = 1)
dans le cas où n > 0 la fonction renvoie n*fact(n-1) (n! = n x (n – 1)!)

On peut essayer de comprendre le fonctionnement du programme ci-dessus à l'aide du schéma suivant :

On a fact(4) = 4 * fact(3) avec fact(3) = 3 * fact(2) avec fact(2) = 2 * fact(1) avec fact(1) = 1 * fact(0) avec fact(0) = 1 (par définition) donc fact(1) = 1 donc fact(2) = 2 donc fact(3) = 6 donc fact(4) = 24

Somme des éléments d'une liste sans boucle for

Les fonctions récursives permettent d'écrire toute sorte d'algorithme sans boucle for.

Il est donc possible de calculer la sommes des éléments d'une liste d'entiers en récursif.

Évaluations restantes : 5/5

.128013it3adv,n2S5éwbcy+14q: f-up0)_elNohrP=[sà6(]/mgk050f0E0c0e0b0F0N0w0p0F0e0N0N0L010c0b0A010406050N0z0T0T0e0J0q040k0H0F0z0:0H0i050S0`0|0~100^0A04051g191j0S1g0^0f0b0g0(0*0,0.0*0i0U0z0e0U0E0y0A0q0c0I170w0I0b0U0I0F1L0I0c0?050Z0o0F0E1s0+0-011K1M1O1M0c1U1W1S0c0J1h1G0(130N0A0e0i0.0j011Y1u010x0#0E0i0e0T0E1S1@1_1~1!211W24260?0a0w0K0J0H0A0H0N0b160i0w0X1=0J0J0E0p2r19290i1h0S1G2E1.1:1/1T0f2b1v0b0i232o1S1p1r0)1Z2O2Q0i0H2U1S0A2x1h2C2E2+0_1^2s2W1 2!0J0}0F1S0e1J2x0x0.030D0D0p2#0E1O2Z0H0y0P0y0s0?0s190e2,2/0@2.2a2;1!2?2^2`2|0E2~01303234362R390y1|040j3f3h1_3j2C2N013o0e2_1h2{0I2}2 31330X3y2!3A0d0?0d3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0t0?0t3%1a3)3k2:1t3n0H2@3N3q3R3s3T3w3W3_3Y3a0l0?0l3 2+3*2/3K3.493=3v3V354f383a0P0?0P4l3i1k2)192U2H0f1:2M3,014u2T1q1h2(0E2*4D403H054u4U2a0b0f0.312C3A3c3P0w4$4(4d4v374+1}2f0E4:4u3X4x3b1S0S3g423K0V0?0X0x3(4X3+440.0n0?0w592D534M0i0x0?0N0H0|0E0D2x0p0z0J2p0g0E5h4!432X010=040Q5A5j5c3L0?1O0N0c5z4W5i5b5D5F0C0v5A0^5R5B4.4%014)2/3A3C3:5$4{3^4?3a1|0w4_5/4e5;3B503g0w5 5g5T1 55040b585!614o4M0H5e042!0c5A693l5K0i5M0b5O5Q2-621!5F5X5!5Z6q4o4/5(0D4*3a3!4-6z3@5`3`0y3!5@254`6A4|4w3Z5}04606V6i5C630?2x0c5v18685J5D0T0b0?0B6h6*1 0p4,030w0*6_6n5P0w0E5O0w0g4$0E0h6_2{5o5q6~700f170p5@0z0F1W5Y5I3J6G6B5*3{3q7m6Q5{3|6M265_4=6J3|2E3g6w4D7l5%5)1_3A4i6F7G4;4}7J4^6N7x7O4h6T6V6;1!6?0?6^0G0H0z0%2n0z0g170%0e0f1p2r2Q0J6_1X0X0J0i0b0E7@0m0F0m260i0c7.5y7e6`78262t1X6`1.1_0p0I7_8d6|1X0u0z0b712{0f0z0w4S6,7~0w0O0w0e0g1_0c8c7{7}7 81836g6v7k6y7M6C397q7M7s6J4z7v6O6H7y4g8R7B6U607X0.646#6%6:6r3-6m6o8N6j5U0?0M8@6Y1!0H0?0y8|3K6,3d924M5F0R8/6a5K8 040r9a8^2=5n5p265s2y5v5x6p7E9b8_5G966k8=5P9v9t0M6u6x9h8~909z1 94043e5!8*5E0?0R0C7j9M0S4Z4E4T4G4Q190c4J9!2K2F0e1V9X0S4H5Z0X0Z0#0N04.

Une chaîne de caractères est-elle un anagramme ?

Pour rappel: un anagramme se lit de la même façon dans les deux sens.

Nous connaissons déjà des algotihmes qui testent si une chaîne est un anagramme.

Nous allons en écrire un qui compare la première et la dernière lettre d'un chaîne et effectue un appel récursif sur la sous-châine restante à tester.

Évaluations restantes : 5/5

.128013Cit3a;dvnîT2SR5éwbcy14q: f-upô8)_09eklohrPè=[sà6(]/mg7050h0K0d0f0c0M0U0z0t0M0f0U0U0S010d0c0D010406050U0C0!0!0f0P0u040n0N0M0C0`0N0j050Z111315170 0D04051n1g1q0Z1n0 0h0c0i0/0;0?0^0;0j0#0C0f0#0K0B0D0u0d0O1e0z0O0c0#0O0M1S0O0d0}050*0s0M0K1z0=0@011R1T1V1T0d1#1%1Z0d0P1o1N0/1a0U0D0f0j0^0m011)1B010A0,0K0j0f0!0K1Z1~20251+281%2b2d0}0a0z0Q0P0N0D0N0U0c1d0j0z0(1|0P0P0K0t2y1g2g0j1o0Z1N2L1^1`1_1!0h2i1C0c0j2a2v1Z1w1y0:1*2V2X0j0N2#1Z0D2E1o2J2L2=101 2z2%262+0P140M1Z0f1Q2E0A0^030H0H0t2,0K1V2*0N0B0$0B0v0}0v1g0f2?2_0~2^2h2{1+2}2 31330K350137393b3d2Y3g0B23040m3m3o203q2J2U013v0f301o320O3436383a0(3F2+3H0e0}0e3M2I3p0 3Q3t0^3T3V053X3Z3B3#3E2W3G3h0w0}0w3.1h3:3r2`1A3u0N2~3U3x3Y3z3!3D3%403)3h0p0}0p462=3;2_3R3^4g3|3C3$3c4m3f3h0W0}0W4s483=4b3@4d3w3W3y3A4A3 3e3H0$0}0$4J3O4u3s4M3S4O4f4Q4h4S3~4l4V3h0F0}0F4!2K1r2:1g2#2O0h1`2T3?014B2!1x1o2/0K2;3p3/3O054B5b2h0c0h0^382J3H3j4Q5j5l4k4C4;3i242m0K5s4B3(4E5w2L3n493R0L0}0(0A5d4`4L2(010r0}0z5N5h4a5Q0j0A0}0K0U0d0H201H0P2c2d5V5H530|040X5/5P2|0}0t0O0+2X5^4v5;0}0G0y5V0 475e3Q5r015m2_3H3J3`0z6b4/5u413I5x2c5z6c5t5C6f1Z0Z5G5_1+5S040z6C5U685O614(0U0h0}02030e0J0g6M6O6Q6N6P66605i5k6r5n3h3+5q6Z6k6t6$6o2d5A4U6m6%3.6y0^6J5T6D0o2a0i0N0c1(0l0P0C1(2w0/5}400z5$0d0z0C2z5*0#5,131(0y0z0q0#3U1(0V0z0;775~1(2E0j0i0K0P0U0q0K6W6F5W6i6)0H6#0B436(6/4:6m430z5y7P6l4n7M6v6x6H5Q6_6B6D0b0)0d1(0A1e2G0c1P1c0,0c0U1(7e0z0f0D0D3c0z0P0q0t0C7B0c0A0z0D1b0d0E7c0x0C6R6P7e1(0s0N0C0:7-4d0z8m0z0r1R1%7F2@6a7J7L4p7O6r5B4D3H4p7T6p7V6+0B8C6?7#267%6D0z8h6T6S8V8x5c8z5s7L4G8D6*8G4F6-6q8*5v8(3M8T5:4(5J04875V5U6@3S0s0}2l6X5X265=5@7G8@5Y5{785 988~5=0G8|99260N6L0M0d0g0S9i8~0!0c3k933R5=657G678y4v6j7K6e3h4X8)6s8+3g8-8L9L9I8=8T6D9j1+8_2E0d851f7G8}8Q9V0t0}72749r9%0^0t5p030/0=2A8k0=75857s5$7u0k2X0.2B0I8r0C0z0v9?5,2G0R2E8Z699D8A9G0B4?9J8F5v4?8J6.8E6:7Xak9R6C9U0^9W0)9Z9-4%5Q969w530j9b7vaG4(5=0TaL5Q9t0}0IaP950}0YaC941+9l040S9q9#ax3SaJ40aY9x0}aO9e9.01a#0BaU1+aR043la=aDaV040Y9ha)8~0N6A200ha.aH5#5%5)2b7h5-7Ea aZ0^aFbk4wa,9d9Cb01+aNa`0^a|a~bsbl019ybwa@0}a_bo53bybE5=b3ae4`0Z5g4{5a4}571g0d50bW2R2M0f1$bT0Z4~670(0*0,0U04.

La suite de Fibonacci⚓︎

L'utilisation des fonctions récursives est souvent liée à la notion de récurrence en mathématiques :

En mathématiques une suite définie par récurrence est une suite définie par son premier terme et par une relation de récurrence, qui définit chaque terme à partir du précédent ou des précédents lorsqu'ils existent.

Prenons l'exemple de la suite de Fibonacci qui est définie par :

u₀ = 0 et u₁ = 1
et par la relation de récurrence suivante avec n entier et n > 1 : u_n = u_n-1 + u_n-2

Ce qui nous donne pour les 6 premiers termes de la suite de Fibonacci :

u₀ = 0
u₁ = 1
u₂ = u₁ + u₀ = 1 + 0 = 1
u₃ = u₂ + u₁ = 1 + 1 = 2
u₄ = u₃ + u₂ = 2 + 1 = 3
u₅ = u₄ + u₃ = 3 + 2 = 5

Code de suite de Fibonacci

Écrire le code qui calcule le n-ième terme de la suite de Fibonacci a l'aide d'un double appel récursif.

Appeler `fibonacci(40)̀ . Que remarque-ton ?