Suite de Fibonacci en récursif (1)

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 :

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.

Calculer des termes de la suite de Fibonacci

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

Exemples :

>>> fibonacci(0)
0
>>> fibonacci(3)
2
>>> fibonacci(7)
13
>>> fibonacci(8)
21
>>> fibonacci(9)
34

On demande ici de programmer une fonction récursive élémentaire, même si son exécution pour des valeurs de $n$ supérieures à $35$ s'avère très lente.

Évaluations restantes : 10/10

.128013à3Bè4.ên/R)p8L0hCvc25A6g%9f=buS-,_l(w?aPkéz;:Vors1qmydi te+050$0*0)0N0%0J0X0(0t0J0N0X0X0C010)0%0m010406050X0E0!0!0N0W0#040F0V0J0E0 0V0i0(020N0!0m0S0(0k0*190W0Z0E0*0X050j16181a1c140m041A1H051K0j1K1M1H140$0%0s0@0_0{0}0q0%0y0q0J1!0q0)12050/0D0J0*1V0`0|011Z1#1%1#0)1-1/1+0)0D0V0$1c1,0W1I0)0q0@1f0X0m0N0i0}0u011;1X010B0;0*0i1n0*1+2c2e2j1?2m1/2p0!2r040a0(0O0W0V0m0V0X0%1i1k0-2a0W0W0*0t2M1A2t0i1I0j282Y0)2625270$2v0}1%0i2o2J1+1S1U0^1=2,0%2.0i221T1+0m2R1I2W2Y33152d1k2@2k2|0W190J120Y2V3713362u391?3b3d120u3h2e3j2W2+013o0N3e040c3s2X143v3m0}3y3A0f3D3u373w3J120v3M1J311A2=2#0$2)3w0t222B0,1T1I300*323i3T3$0-3.3l1W1?0P120-0B3T3G3^0}0L120(3~3O3H3x0B122m212p0t0t0%453@2^0111040K4h38403x120i4o3w4l0l0T3M060(4B443 4j3`040%3}1B3i4D464q0i4s3M4M4i2k0V12020J0)0S4R3k4p4j0!0%3q4u474l4y4K3t4A4C4?4$3w4G2R0)0E0W4t4:2X4S4%3a4Q50134@4E2k4G0*0=0*4,4q4.4z4?584N4F124{4}4 33523P4a0%4c0N4e4g564^4-124n5A593n555r5B4q4V040G4#5G0}4)3f5f4j4w5P5l4U120+5X4T5H044b1j5x4f5U2k4l5E355Q4r045q4L5K4j5M5O565s475S043r5F5Y1?5W56140j3;3-3U6d0j3X1A0)3Z6i2%2Z21232#0N1.6f3X1G3?531?2R0!0I0B0N0P0*0I0q0c121s1u1w1y0(4/351N3j1H0o0N0(0B1j2T0%1j0(300Q0t0Q0-0i0)1:0-0s0%2o0)0(2$0e0?2y6-0(0b6$1a0 0W0(2O056c5^0(0C0(0c3S6b3%040(2o6:2G0i0H0@1a0(1/0?0!0h2A0?0t3z0t0E0=0(0X1j6?0W0Q0m0Q0)0Q0?2O6^0?2|0!0D2R0E0X6N6X0%0X0g446R6v056V0q2R0B1Y1|0m0X0T0j0j0L7=0g2R7x0W2K1j6:163z0%0R0*0W0g3$0!0j0M0B0E0i6Z1j0I3|2`2L6!2f3|0z0u0p5*4d4f8l0n0i8l0A0z0c0w0z0p8y8m8l0p8D8D4I8D8t8C0c0r8D0u8w8y8A8F8C8T8E8U8S0p5o4~8I8z8B8V8(8D5c7T8P8$8X8/8W8U8Z8J8n5v5+5y8r8@0G8D0Y8u8S0d8D8o5,0%8|8D8~8m8O0u0A1m1o0S898b2M0I7v0J0J0C958{0u0n0x8u2i0/0W0y0.0}0I1.2e4G0U7W0E7 0X0N2M6$0V4}7o000N0m0m5c731:9q4f0K0x0l1A0N2Y1Q3W0.0:0=04.

Compter le nombre d'appels

Nous avons vu dans la remarque de la question précédente que cette fonction devenait très lente à partir de n = 35 environ, car les mêmes calculs étaient répétés de très nombreuses fois.
Par exemple le terme de rang 9 vaut 34 et nécessite 109 appels. Pour visualiser ces nombreux appels, suivre le lien Tous les appels pour le calcul de fibonacci(6).

Le but de cette question est d'écrire une fonction fibonacci_valeurs_appels basée sur le même principe, mais qui renvoie également le nombre d'appels nécessaires. Cette fonction prend en paramètre un entier n et renvoie un tuple (valeur, appels) dont le premier terme est la valeur du terme de rang n de la suite de Fibonacci et le second le nombre d'appels qu'il a été nécessaire d'effectuer.

Exemples :

>>> fibonacci_valeurs_appels(0)
(0, 1)
>>> fibonacci_valeurs_appels(3)
(2, 5)
>>> fibonacci_valeurs_appels(6)
(8, 25)
>>> fibonacci_valeurs_appels(9)
(34, 109)
>>> fibonacci_valeurs_appels(30)
(832040, 2692537)

Évaluations restantes : 10/10

.128013[34.nx/R8p)L0hv7c256g9f=buS-,_l(w^aPké;:ors1qmyd]i{ }te+050W0%0$0J0Y0F0R0!0r0F0J0R0R0y010$0Y0k010406050R0A0U0U0J0Q0V040B0P0F0A0|0P0f0!020J0U0k0N0!0i0%160Q0T0A0%0R050h13151719110k041x1E051H0h1H1J1E110W0Y0p0;0?0^0`0o0Y0v0o0F1X0o0$0 050,0z0F0%1S0@0_011W1Y1!1Y0$1*1,1(0$0z0P0W191)0Q1F0$0o0;1c0R0k0J0f0`0s011.1U010x0.0%0f1k0%1(292b2g1:2j1,2m0U2o040a0!0K0Q0P0k0P0R0Y1f1h0*270Q0Q0%0r2J1x2q0f1F0h252V0$2322240W2s0`1!0f2l2G1(1P1R0=1/2)0Y2+0f1 1Q1(0k2O1F2T2V30122a1h2;2h2_0Q160F0 0S2S3410332r361:383a0 0s3e2b3g2T2(013l0J3b040c3p2U113s3j0`3v3x0d3A3r343t3G0 0t3J3C3L3E3u0P393w0 0u3Q3h351T3k3V3m040q3!3D3%3F3)3X040j3-3S3/3U3W3x0w3J1G2~1x2/2Y0W2$3t0r1 2y0)1Q1F2}0%2 3f3 480*4g3i3`0L0 0*0x3 3.2=010H0 0!4s3_4u0f0x0 2j1~2m0r0r0Y0E0p3w0%0A0Q0R0E0J0k0k0%0/4z4m4u0~040G4Y3$4B0 0f4(3t4#0l0O3Q0!4?4y4t2h4o040Y4r1y3f4^4A374+3J514Z2h0P0 0y0y553#3t0U0Y0 0n4-3T4#4;4 3q064@5r564)4`0 2O0$4P4,5o2U5t5f5h045j5B4l5u1:4#0D5d4_1:5g3c4=4@5e3T4{4W4}5O523k545I5D3T59045b5!575Q5F3d5I5V3`5m5T5s5)4n5w0+5z5.5K0`5R045=325P0`5M615E5S5I5q5U68015X0/0%5k5^0 5n306f5{5@4*040p664h6h6a5(6t53040r6x3q5|4u5+5c6B6h0f4E0Y4G0J4I4K4M1,4P4R4T4V4X5?6z0 4%6$5#3F5%306I580 0C6b3T646G2U6C5L0 0l5`5s6{6,6v3o6*5/690 5N6M6+3u0 0r746.71016K6?3`6O044F1g6S4J4L4N6X4S4U4W1w7562014#6)677b7m5A7g6h5+6=7a7601647f6y7b4/6 5r7h4{5x607M7A7m6w7k6J0 0(7(6D0p7Q3q7h6A7I7b6^7,1:5+7+7!3M7d6_046/7`7*7_727e3!0h4j4f408b0h431x0$458g2!2W1~202Y0J1+8d431D5J3t2O0U0E0x0J0L0%0E0o0c0 1p1r1t1v0!6p4h1K3g1E0m1-2_0U0z2O0!0W006Z7x0!2F4P0;3w0r0A1,0Q4y8a7n6Q7p6T0b0f0X1x8:8$0P8(2L0v0Q2b0*0:6V4O4Q8X1-058:5A8|1v0$8X002l0p0Y2D1h7h172I0o160$0%0g0 090G090k1W0!0I0f096~5(0J0p2P820`9p259s9u9w9y9A0Y0!0y0!090W0x920r0Z0S0(9X0R0T0Q0$0Z0t0#0#0Z0s0#9F3J0e4y8O8t9o0Q9q9P9v049x9z1W9_5(9f0!8!0F0M0!3U8U8W8Y3V019{1G8P040K8~8.9b49041h9W0c5H8:0D0!0.0!8z1e0!9j9l1g990A0g0!5g0F1!1g0:8Yac0R0ean118e0+0-0/04.