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

.128013s3_8èufvy naêS1me(P24C:Vtwih)6o;bcdg?/0làqABp.rL-,=+zk%95Ré050J0r0z0m0B0O0b0k0I0O0m0b0b0Z010z0B0T010406050b0g0q0q0m0V0j040o0F0O0g0 0F0l0k020m0q0T0G0k0*0r190V0Q0g0r0b050M16181a1c140T041A1H051K0M1K1M1H140J0B0i0@0_0{0}0C0B0K0C0O1!0C0z12050/0H0O0r1V0`0|011Z1#1%1#0z1-1/1+0z0H0F0J1c1,0V1I0z0C0@1f0b0T0m0l0}0u011;1X010h0;0r0l1n0r1+2c2e2j1?2m1/2p0q2r040a0k0t0V0F0T0F0b0B1i1k0-2a0V0V0r0I2M1A2t0l1I0M282Y0z2625270J2v0}1%0l2o2J1+1S1U0^1=2,0B2.0l221T1+0T2R1I2W2Y33152d1k2@2k2|0V190O120p2V3713362u391?3b3d120u3h2e3j2W2+013o0m3e040c3s2X143v3m0}3y3A0v3D3u373w3J120)3M1J311A2=2#0J2)3w0I222B0,1T1I300r323i3T3$0-3.3l1W1?0$120-0h3T3G3^0}0A120k3~3O3H3x0h122m212p0I0I0B453@2^0111040s4h38403x120l4o3w4l0D0x3M060k4B443 4j3`040B3}1B3i4D464q0l4s3M4M4i2k0F12020O0z0G4R3k4p4j0q0B3q4u474l4y4K3t4A4C4?4$3w4G2R0z0g0V4t4:2X4S4%3a4Q50134@4E2k4G0r0=0r4,4q4.4z4?584N4F124{4}4 33523P4a0B4c0m4e4g564^4-124n5A593n555r5B4q4V040X4#5G0}4)3f5f4j4w5P5l4U120!5X4T5H044b1j5x4f5U2k4l5E355Q4r045q4L5K4j5M5O565s475S043r5F5Y1?5W56140M3;3-3U6d0M3X1A0z3Z6i2%2Z21232#0m1.6f3X1G3?531?2R0q0d0h0m0$0r0d0C0c121s1u1w1y0k4/351N3j1H0W0m0k0h1j2T0B1j0k300+0I0+0-0l0z1:0-0i0B2o0z0k2$0f0?2y6-0k0P6$1a0 0V0k2O056c5^0k0Z0k0c3S6b3%040k2o6:2G0l0Y0@1a0k1/0?0q0n2A0?0I3z0I0g0=0k0b1j6?0V0+0T0+0z0+0?2O6^0?2|0q0H2R0g0b6N6X0B0b0U446R6v056V0C2R0h1Y1|0T0b0x0M0M0A7=0U2R7x0V2K1j6:163z0B0#0r0V0U3$0q0M0L0h0g0l6Z1j0d3|2`2L6!2f3|0%0u0N5*4d4f8l0e0l8l0(0%0c0R0%0N8y8m8l0N8D8D4I8D8t8C0c0w8D0u8w8y8A8F8C8T8E8U8S0N5o4~8I8z8B8V8(8D5c7T8P8$8X8/8W8U8Z8J8n5v5+5y8r8@0X8D0p8u8S0S8D8o5,0B8|8D8~8m8O0u0(1m1o0G898b2M0d7v0O0O0Z958{0u0e0E8u2i0/0V0K0.0}0d1.2e4G0y7W0g7 0b0m2M6$0F4}7o000m0T0T5c731:9q4f0s0E0D1A0m2Y1Q3W0.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

.128013s3_8uf^vy n7aS1me(P24:twi][h)6o;bcdgx/0lqp.rL-,}=+k95R{é050J0r0x0n0z0O0b0k0I0O0n0b0b0X010x0z0Q010406050b0f0q0q0n0S0j040o0F0O0f0|0F0l0k020n0q0Q0G0k0$0r160S0P0f0r0b050M13151719110Q041x1E051H0M1H1J1E110J0z0i0;0?0^0`0C0z0K0C0O1X0C0x0 050,0H0O0r1S0@0_011W1Y1!1Y0x1*1,1(0x0H0F0J191)0S1F0x0C0;1c0b0Q0n0l0`0u011.1U010g0.0r0l1k0r1(292b2g1:2j1,2m0q2o040a0k0t0S0F0Q0F0b0z1f1h0*270S0S0r0I2J1x2q0l1F0M252V0x2322240J2s0`1!0l2l2G1(1P1R0=1/2)0z2+0l1 1Q1(0Q2O1F2T2V30122a1h2;2h2_0S160O0 0p2S3410332r361:383a0 0u3e2b3g2T2(013l0n3b040c3p2U113s3j0`3v3x0v3A3r343t3G0 0#3J3C3L3E3u0F393w0 0E3Q3h351T3k3V3m040m3!3D3%3F3)3X040e3-3S3/3U3W3x0!3J1G2~1x2/2Y0J2$3t0I1 2y0)1Q1F2}0r2 3f3 480*4g3i3`0Z0 0*0g3 3.2=010y0 0k4s3_4u0l0g0 2j1~2m0I0I0z0d0i3w0r0f0S0b0d0n0Q0Q0r0/4z4m4u0~040s4Y3$4B0 0l4(3t4#0D0w3Q0k4?4y4t2h4o040z4r1y3f4^4A374+3J514Z2h0F0 0X0X553#3t0q0z0 0N4-3T4#4;4 3q064@5r564)4`0 2O0x4P4,5o2U5t5f5h045j5B4l5u1:4#0V5d4_1:5g3c4=4@5e3T4{4W4}5O523k545I5D3T59045b5!575Q5F3d5I5V3`5m5T5s5)4n5w0+5z5.5K0`5R045=325P0`5M615E5S5I5q5U68015X0/0r5k5^0 5n306f5{5@4*040i664h6h6a5(6t53040I6x3q5|4u5+5c6B6h0l4E0z4G0n4I4K4M1,4P4R4T4V4X5?6z0 4%6$5#3F5%306I580 0U6b3T646G2U6C5L0 0D5`5s6{6,6v3o6*5/690 5N6M6+3u0 0I746.71016K6?3`6O044F1g6S4J4L4N6X4S4U4W1w7562014#6)677b7m5A7g6h5+6=7a7601647f6y7b4/6 5r7h4{5x607M7A7m6w7k6J0 0Y7(6D0i7Q3q7h6A7I7b6^7,1:5+7+7!3M7d6_046/7`7*7_727e3!0M4j4f408b0M431x0x458g2!2W1~202Y0n1+8d431D5J3t2O0q0d0g0n0Z0r0d0C0c0 1p1r1t1v0k6p4h1K3g1E0T1-2_0q0H2O0k0J006Z7x0k2F4P0;3w0I0f1,0S4y8a7n6Q7p6T0B0l0A1x8:8$0F8(2L0K0S2b0*0:6V4O4Q8X1-058:5A8|1v0x8X002l0i0z2D1h7h172I0C160x0r0L0 090s090Q1W0k0h0l096~5(0n0i2P820`9p259s9u9w9y9A0z0k0X0k090J0g920I0%0p0Y9X0b0P0S0x0%0#0W0W0%0u0W9F3J0R4y8O8t9o0S9q9P9v049x9z1W9_5(9f0k8!0O0(0k3U8U8W8Y3V019{1G8P040t8~8.9b49041h9W0c5H8:0V0k0.0k8z1e0k9j9l1g990f0L0k5g0O1!1g0:8Yac0b0Ran118e0+0-0/04.