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,%è Vw5e(?z8CR0pkoic6S1vqAd:y24fln-9B3m=)rhêus;b/.àt_gLéaP+050B0i0!0)0t0H0U0e0u0H0)0U0U0O010!0t0q010406050U0T0N0N0)0Q0D040w0s0H0T0 0s0I0e020)0N0q0V0e0o0i190Q0z0T0i0U050X16181a1c140q041A1H051K0X1K1M1H140B0t0y0@0_0{0}0R0t0$0R0H1!0R0!12050/0W0H0i1V0`0|011Z1#1%1#0!1-1/1+0!0W0s0B1c1,0Q1I0!0R0@1f0U0q0)0I0}0E011;1X010G0;0i0I1n0i1+2c2e2j1?2m1/2p0N2r040a0e0*0Q0s0q0s0U0t1i1k0-2a0Q0Q0i0u2M1A2t0I1I0X282Y0!2625270B2v0}1%0I2o2J1+1S1U0^1=2,0t2.0I221T1+0q2R1I2W2Y33152d1k2@2k2|0Q190H120x2V3713362u391?3b3d120E3h2e3j2W2+013o0)3e040M3s2X143v3m0}3y3A0F3D3u373w3J120h3M1J311A2=2#0B2)3w0u222B0,1T1I300i323i3T3$0-3.3l1W1?0r120-0G3T3G3^0}0g120e3~3O3H3x0G122m212p0u0u0t453@2^0111040j4h38403x120I4o3w4l0P0C3M060e4B443 4j3`040t3}1B3i4D464q0I4s3M4M4i2k0s12020H0!0V4R3k4p4j0N0t3q4u474l4y4K3t4A4C4?4$3w4G2R0!0T0Q4t4:2X4S4%3a4Q50134@4E2k4G0i0=0i4,4q4.4z4?584N4F124{4}4 33523P4a0t4c0)4e4g564^4-124n5A593n555r5B4q4V040J4#5G0}4)3f5f4j4w5P5l4U120+5X4T5H044b1j5x4f5U2k4l5E355Q4r045q4L5K4j5M5O565s475S043r5F5Y1?5W56140X3;3-3U6d0X3X1A0!3Z6i2%2Z21232#0)1.6f3X1G3?531?2R0N0#0G0)0r0i0#0R0M121s1u1w1y0e4/351N3j1H0%0)0e0G1j2T0t1j0e300(0u0(0-0I0!1:0-0y0t2o0!0e2$0d0?2y6-0e0Z6$1a0 0Q0e2O056c5^0e0O0e0M3S6b3%040e2o6:2G0I0b0@1a0e1/0?0N0S2A0?0u3z0u0T0=0e0U1j6?0Q0(0q0(0!0(0?2O6^0?2|0N0W2R0T0U6N6X0t0U0Y446R6v056V0R2R0G1Y1|0q0U0C0X0X0g7=0Y2R7x0Q2K1j6:163z0t0l0i0Q0Y3$0N0X0k0G0T0I6Z1j0#3|2`2L6!2f3|0c0E0p5*4d4f8l0m0I8l0K0c0M0A0c0p8y8m8l0p8D8D4I8D8t8C0M0n8D0E8w8y8A8F8C8T8E8U8S0p5o4~8I8z8B8V8(8D5c7T8P8$8X8/8W8U8Z8J8n5v5+5y8r8@0J8D0x8u8S0L8D8o5,0t8|8D8~8m8O0E0K1m1o0V898b2M0#7v0H0H0O958{0E0m0v8u2i0/0Q0$0.0}0#1.2e4G0f7W0T7 0U0)2M6$0s4}7o000)0q0q5c731:9q4f0j0v0P1A0)2Y1Q3W0.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, w5e(8R0pkoic6S1vq{d:xy24fln-]93m=)rh[u}s;^b/.t_gLéaP+7050v0f0W0#0n0C0Q0c0o0C0#0Q0Q0J010W0n0k010406050Q0O0I0I0#0L0y040q0m0C0O0|0m0D0c020#0I0k0R0c0i0f160L0t0O0f0Q050U13151719110k041x1E051H0U1H1J1E110v0n0s0;0?0^0`0M0n0Y0M0C1X0M0W0 050,0T0C0f1S0@0_011W1Y1!1Y0W1*1,1(0W0T0m0v191)0L1F0W0M0;1c0Q0k0#0D0`0z011.1U010B0.0f0D1k0f1(292b2g1:2j1,2m0I2o040a0c0$0L0m0k0m0Q0n1f1h0*270L0L0f0o2J1x2q0D1F0U252V0W2322240v2s0`1!0D2l2G1(1P1R0=1/2)0n2+0D1 1Q1(0k2O1F2T2V30122a1h2;2h2_0L160C0 0r2S3410332r361:383a0 0z3e2b3g2T2(013l0#3b040H3p2U113s3j0`3v3x0A3A3r343t3G0 0e3J3C3L3E3u0m393w0 0p3Q3h351T3k3V3m040(3!3D3%3F3)3X040h3-3S3/3U3W3x0G3J1G2~1x2/2Y0v2$3t0o1 2y0)1Q1F2}0f2 3f3 480*4g3i3`0l0 0*0B3 3.2=010d0 0c4s3_4u0D0B0 2j1~2m0o0o0n0X0s3w0f0O0L0Q0X0#0k0k0f0/4z4m4u0~040g4Y3$4B0 0D4(3t4#0K0w3Q0c4?4y4t2h4o040n4r1y3f4^4A374+3J514Z2h0m0 0J0J553#3t0I0n0 0j4-3T4#4;4 3q064@5r564)4`0 2O0W4P4,5o2U5t5f5h045j5B4l5u1:4#0b5d4_1:5g3c4=4@5e3T4{4W4}5O523k545I5D3T59045b5!575Q5F3d5I5V3`5m5T5s5)4n5w0+5z5.5K0`5R045=325P0`5M615E5S5I5q5U68015X0/0f5k5^0 5n306f5{5@4*040s664h6h6a5(6t53040o6x3q5|4u5+5c6B6h0D4E0n4G0#4I4K4M1,4P4R4T4V4X5?6z0 4%6$5#3F5%306I580 0E6b3T646G2U6C5L0 0K5`5s6{6,6v3o6*5/690 5N6M6+3u0 0o746.71016K6?3`6O044F1g6S4J4L4N6X4S4U4W1w7562014#6)677b7m5A7g6h5+6=7a7601647f6y7b4/6 5r7h4{5x607M7A7m6w7k6J0 0%7(6D0s7Q3q7h6A7I7b6^7,1:5+7+7!3M7d6_046/7`7*7_727e3!0U4j4f408b0U431x0W458g2!2W1~202Y0#1+8d431D5J3t2O0I0X0B0#0l0f0X0M0H0 1p1r1t1v0c6p4h1K3g1E0Z1-2_0I0T2O0c0v006Z7x0c2F4P0;3w0o0O1,0L4y8a7n6Q7p6T0N0D0F1x8:8$0m8(2L0Y0L2b0*0:6V4O4Q8X1-058:5A8|1v0W8X002l0s0n2D1h7h172I0M160W0f0x0 090g090k1W0c0S0D096~5(0#0s2P820`9p259s9u9w9y9A0n0c0J0c090v0B920o0u0r0%9X0Q0t0L0W0u0e0P0P0u0z0P9F3J0V4y8O8t9o0L9q9P9v049x9z1W9_5(9f0c8!0C0!0c3U8U8W8Y3V019{1G8P040$8~8.9b49041h9W0H5H8:0b0c0.0c8z1e0c9j9l1g990O0x0c5g0C1!1g0:8Yac0Q0Van118e0+0-0/04.