Suite de Fibonacci en récursif (2)

Source : Wikimedia Commons, domaine public, A portfolio of portraits of eminent mathematicians, 1905.

Série d'exercices

Cet exercice fait partie d'une série :

• Suite de Fibonacci en itératif (1)
• Suite de Fibonacci en itératif (2)
• Suite de Fibonacci en récursif (1)
• Suite de Fibonacci en récursif (2)

La suite dite "suite de Fibonacci" est une suite d'entiers qui commence par 0 et 1. Chacun des autres termes est la somme des deux précédents : ainsi les termes suivants sont 1 (car 0 + 1 = 1), 2 (car 1 + 1 = 2), puis 3 (car 1 + 2 = 3) et ainsi de suite. Les premiers termes sont donc : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

On dit que le terme d’indice 0 est \(u_0=0\), celui d’indice 1 est \(u_1=1\), celui d’indice 2 est \(u_2=1\) … celui d’indice 7 est \(u_7=13\) etc.

Compléter la fonction fibonacciqui prend en paramètre un entier n et renvoie le terme d'indice n de la suite de Fibonacci.

La fonction récursive naïve présentée dans l'exercice Suite de Fibonacci en récursif (1) devient très lente à parir de n = 35 environ, car les mêmes calculs sont répétés de très nombreuses fois.

Pour éviter cela, on peut stocker les valeurs déjà calculées dans un dictionnaire. On applique ici une approche descendante de la programmation dynamique.

Dans la version à compléter les ... peuvent représenter une ou plusieurs lignes.

Version vide Version à compléter

###(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 : 10/10

.1280135[4})2R,%Ba- iV8m16Cl7.eï:9A;S/dktf{+r?T3sogu0x]PpOnh=céyvDz(wq_b050G0y0I0l0o0v0Q0n0%0v0l0Q0Q0$010I0o0Y010406050Q0T0r0r0l0M0)040E0R0v0T150R0!0n020l0r0Y0D0n0h0y1f0M0/0T0y0Q050F1c1e1g1i1a0Y041G1N051Q0F1Q1S1N1a0G0o0*0}0 11130#0o0S0#0v1*0#0I18050^0;0v0y1#1012011)1+1-1+0I1?1^1;0I0;0R0G1i1=0M1O0I0#0}1l0Q0Y0l0!130g011`1%010J0`0y0!1t0y1;2i2k2p1|2s1^2v0r2x040a0n0X0M0R0Y0R0Q0o1o1q0?2g0M0M0y0%2S1G2z0!1O0F2e2(0I2c2b2d0G2B131-0!2u2P1;1Y1!0~1{2=0o2@0!281Z1;0Y2X1O2$2(391b2j1q2}2q320M1f0v180n0s2#3d193c2A3f1|3h3j3l0g3o2k3q2$2;013v0l3k040n0P3z2%1a3C3t133F3H0n0d3L3B3d3D3R3l0b3V3N3X3P3E0R3i3G3l0t3$3r3e1$3u3+3w3I0w3:3O3?3Q3^3-3I0q3|3(3~3*3,3S0B443s463Z040s0U4b3=2~473_0s3n1H3p3%4c4k4e0s3y4p3A4r4j3g403H0s3K4x2%1P371G2{2+0G2/3D0%282H0=1Z1O360y383p3V054Q0?4Y4s3g182G0r0R3V0n3;3D0R180$4/4;3)17040K0e3$4z3D0H180?0J4!3}4k0.3l57454t0J182s272v0%0%0o5c4)1|4|0-5n4A3u180!5s3D4|0f0A3$0n5D4:582q0%0s18030n0Z1q0I1E5P0n0 0n360(0Q2u0%1_0G2k0|4,4.4G195E5F5d2q53040o565*5-5o3Q5v4_5G1|0R5a5;5w5@4`4d4+1z5)3b5}134|5B5@5^5t135I5K0n0E0o5U0M5W5Y1_1p0n2X0!0*0R0o1_5T0*3G0y0T0M5C5,5E644k5:2X0I6E62396f3Y664-5x4{180c6V65046P4Z6a014|0W6G5D6J5H5J045L6l0n0l0;5X0!5Z0i0n6s0%3G0%0T1^5U0T0o0|6s0r0(4-0M776z1_6o1c0v0^0I6,6R3)5:5=5|5.5u6#7r5_014?040$4^636(0r0o184h7C7s135 183+7v6g3E5{7I7w7y7A7O3D7E184o697J6)186d6Q7n466i6;0n0u100n2U0;100y7m5,6.7t5h0:6$3A7+4k7U7W3)0!7R39067{6(5:0y0{7_5*7|6b7(7`6I6(87047~802%822q847S7P8o5h1p0l5k5m8h6(5q6Z4t886%7$7y0m8H2q7Y4f8O5p180f85467y0L8W8I8p0o5i8B5l8S8j045r8E7$8o8r4(7P8M8+018Q4w7#7w5z4/8t1|7-5L0C0Y0Y8e6t0(720M2Q5?898b8:6T688K8~6X8_8;8_6*8!8u4@9r7}8%7 908i01930n7a7c770l2!5*8a8m7$6L0@6O9u5`8$0;9x9I1G4$4X4I9X0F4L1G0I4N9$2-2)27292+6^1^2(4L1M8?3D2X0r0:0J0l0H0y0:0#0P181y1A1C1E0n7)4Z1T3q1Q0l0n0#2X0J1(220Y0Q0A0F0F0.aq0x2X9b2Q1p0*770T3G0o0,0y0M0x4Q0r0F0N0J0T6{2S0:55302R0o1p0$5(0j0g0U0j0P0+aWaY0w0k0j0wa#0U0C0ja-55a$8z5j5laW0q0!aW0BaZa.a-a$b1aXb20Pa$5Na$5P0Q5Pa$0 a$360j0ub50C0B6`5Za$5#0!0Qbc0ya$0rbgbi0B4-a/a.b3bBaYaX5=a$a{bEbH0UaV0Pa bAbDbPb2bQbC6M6Obt670j0b0ka{0ba,bObRb4a$6la$6^blbs0g0ua$1pa$700v721^bzb)bCbFaXbJaZa#a!a$bP3+bGb1c5c5aX0sa~b~b5aX7:bqaX0?a$7@5Xb}bCb~bSbP8qcaa#c1cqcta$8ecpbMczcscGaXcvb3cc0Ua?8)0oa_0!0mce0ga}bBa)cI8%8A8CcQ0m0ga|cga$95970va$0Mbv0jbjaubFb0crbCaVbZb#cxaYcLcvc_cAaXbU0MbJ8q1s1u0DaKaMaS0!0:b_0v0$cNc#0g0q0ta|2o0^0M0S0@130:1@2k5:0payaA0Q9Gdf5U0R6E5S000l96982Udl5l0-0t0fdHdJ5Z221_0*aDav1q0ld!0%9C7b0R0zdE9H0l2(1W1R045N2gbp7k1_0;6y1qa65Sa7320r0;2X0T0V0}71730|2X0G1pbo0I780!0I0n0(0I0(emaxeo0Q0x1Pacd^d%0n0o5l0n1n0`77epaL1_dM360R0%0#eIdN0v0(1_010O2N0m0+5 87ev1a9!0@0_0{04.

###(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 : 10/10

.1280135[4})2R,%Ba- iV8m16Cl7.eï:9A;S/dktf{+r?T3sogu0x]PpOnh=céyvDz(wq_b050G0y0I0l0o0v0Q0n0%0v0l0Q0Q0$010I0o0Y010406050Q0T0r0r0l0M0)040E0R0v0T150R0!0n020l0r0Y0D0n0h0y1f0M0/0T0y0Q050F1c1e1g1i1a0Y041G1N051Q0F1Q1S1N1a0G0o0*0}0 11130#0o0S0#0v1*0#0I18050^0;0v0y1#1012011)1+1-1+0I1?1^1;0I0;0R0G1i1=0M1O0I0#0}1l0Q0Y0l0!130g011`1%010J0`0y0!1t0y1;2i2k2p1|2s1^2v0r2x040a0n0X0M0R0Y0R0Q0o1o1q0?2g0M0M0y0%2S1G2z0!1O0F2e2(0I2c2b2d0G2B131-0!2u2P1;1Y1!0~1{2=0o2@0!281Z1;0Y2X1O2$2(391b2j1q2}2q320M1f0v180n0s2#3d193c2A3f1|3h3j3l0g3o2k3q2$2;013v0l3k040n0P3z2%1a3C3t133F3H0n0d3L3B3d3D3R3l0b3V3N3X3P3E0R3i3G3l0t3$3r3e1$3u3+3w3I0w3:3O3?3Q3^3-3I0q3|3(3~3*3,3S0B443s463Z040s0U4b3=2~473_0s3n1H3p3%4c4k4e0s3y4p3A4r4j3g403H0s3K4x2%1P371G2{2+0G2/3D0%282H0=1Z1O360y383p3V054Q0?4Y4s3g182G0r0R3V0n3;3D0R180$4/4;3)17040K0e3$4z3D0H180?0J4!3}4k0.3l57454t0J182s272v0%0%0o5c4)1|4|0-5n4A3u180!5s3D4|0f0A3$0n5D4:582q0%0s18030n0Z1q0I1E5P0n0 0n360(0Q2u0%1_0G2k0|4,4.4G195E5F5d2q53040o565*5-5o3Q5v4_5G1|0R5a5;5w5@4`4d4+1z5)3b5}134|5B5@5^5t135I5K0n0E0o5U0M5W5Y1_1p0n2X0!0*0R0o1_5T0*3G0y0T0M5C5,5E644k5:2X0I6E62396f3Y664-5x4{180c6V65046P4Z6a014|0W6G5D6J5H5J045L6l0n0l0;5X0!5Z0i0n6s0%3G0%0T1^5U0T0o0|6s0r0(4-0M776z1_6o1c0v0^0I6,6R3)5:5=5|5.5u6#7r5_014?040$4^636(0r0o184h7C7s135 183+7v6g3E5{7I7w7y7A7O3D7E184o697J6)186d6Q7n466i6;0n0u100n2U0;100y7m5,6.7t5h0:6$3A7+4k7U7W3)0!7R39067{6(5:0y0{7_5*7|6b7(7`6I6(87047~802%822q847S7P8o5h1p0l5k5m8h6(5q6Z4t886%7$7y0m8H2q7Y4f8O5p180f85467y0L8W8I8p0o5i8B5l8S8j045r8E7$8o8r4(7P8M8+018Q4w7#7w5z4/8t1|7-5L0C0Y0Y8e6t0(720M2Q5?898b8:6T688K8~6X8_8;8_6*8!8u4@9r7}8%7 908i01930n7a7c770l2!5*8a8m7$6L0@6O9u5`8$0;9x9I1G4$4X4I9X0F4L1G0I4N9$2-2)27292+6^1^2(4L1M8?3D2X0r0:0J0l0H0y0:0#0P181y1A1C1E0n7)4Z1T3q1Q0l0n0#2X0J1(220Y0Q0A0F0F0.aq0x2X9b2Q1p0*770T3G0o0,0y0M0x4Q0r0F0N0J0T6{2S0:55302R0o1p0$5(0j0g0U0j0P0+aWaY0w0k0j0wa#0U0C0ja-55a$8z5j5laW0q0!aW0BaZa.a-a$b1aXb20Pa$5Na$5P0Q5Pa$0 a$360j0ub50C0B6`5Za$5#0!0Qbc0ya$0rbgbi0B4-a/a.b3bBaYaX5=a$a{bEbH0UaV0Pa bAbDbPb2bQbC6M6Obt670j0b0ka{0ba,bObRb4a$6la$6^blbs0g0ua$1pa$700v721^bzb)bCbFaXbJaZa#a!a$bP3+bGb1c5c5aX0sa~b~b5aX7:bqaX0?a$7@5Xb}bCb~bSbP8qcaa#c1cqcta$8ecpbMczcscGaXcvb3cc0Ua?8)0oa_0!0mce0ga}bBa)cI8%8A8CcQ0m0ga|cga$95970va$0Mbv0jbjaubFb0crbCaVbZb#cxaYcLcvc_cAaXbU0MbJ8q1s1u0DaKaMaS0!0:b_0v0$cNc#0g0q0ta|2o0^0M0S0@130:1@2k5:0payaA0Q9Gdf5U0R6E5S000l96982Udl5l0-0t0fdHdJ5Z221_0*aDav1q0ld!0%9C7b0R0zdE9H0l2(1W1R045N2gbp7k1_0;6y1qa65Sa7320r0;2X0T0V0}71730|2X0G1pbo0I780!0I0n0(0I0(emaxeo0Q0x1Pacd^d%0n0o5l0n1n0`77epaL1_dM360R0%0#eIdN0v0(1_010O2N0m0+5 87ev1a9!0@0_0{04.