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

.128013nm%wgPoC,6uRèa8bsrvcez-1SB9_d(Liyk02; V5à+l4t/.3)Afh:?=êéqp050D0v0T0o0G0R0r0M0u0R0o0r0r0%010T0G0+010406050r0l0c0c0o0s0H040z0h0R0l0 0h0b0M020o0c0+0L0M0m0v190s0*0l0v0r050U16181a1c140+041A1H051K0U1K1M1H140D0G0t0@0_0{0}0!0G0f0!0R1!0!0T12050/0q0R0v1V0`0|011Z1#1%1#0T1-1/1+0T0q0h0D1c1,0s1I0T0!0@1f0r0+0o0b0}0K011;1X010Z0;0v0b1n0v1+2c2e2j1?2m1/2p0c2r040a0M0g0s0h0+0h0r0G1i1k0-2a0s0s0v0u2M1A2t0b1I0U282Y0T2625270D2v0}1%0b2o2J1+1S1U0^1=2,0G2.0b221T1+0+2R1I2W2Y33152d1k2@2k2|0s190R120y2V3713362u391?3b3d120K3h2e3j2W2+013o0o3e040W3s2X143v3m0}3y3A0S3D3u373w3J120O3M1J311A2=2#0D2)3w0u222B0,1T1I300v323i3T3$0-3.3l1W1?0I120-0Z3T3G3^0}0e120M3~3O3H3x0Z122m212p0u0u0G453@2^0111040E4h38403x120b4o3w4l0X0#3M060M4B443 4j3`040G3}1B3i4D464q0b4s3M4M4i2k0h12020R0T0L4R3k4p4j0c0G3q4u474l4y4K3t4A4C4?4$3w4G2R0T0l0s4t4:2X4S4%3a4Q50134@4E2k4G0v0=0v4,4q4.4z4?584N4F124{4}4 33523P4a0G4c0o4e4g564^4-124n5A593n555r5B4q4V040x4#5G0}4)3f5f4j4w5P5l4U120Q5X4T5H044b1j5x4f5U2k4l5E355Q4r045q4L5K4j5M5O565s475S043r5F5Y1?5W56140U3;3-3U6d0U3X1A0T3Z6i2%2Z21232#0o1.6f3X1G3?531?2R0c0C0Z0o0I0v0C0!0W121s1u1w1y0M4/351N3j1H0F0o0M0Z1j2T0G1j0M300)0u0)0-0b0T1:0-0t0G2o0T0M2$0n0?2y6-0M0P6$1a0 0s0M2O056c5^0M0%0M0W3S6b3%040M2o6:2G0b0j0@1a0M1/0?0c0(2A0?0u3z0u0l0=0M0r1j6?0s0)0+0)0T0)0?2O6^0?2|0c0q2R0l0r6N6X0G0r0V446R6v056V0!2R0Z1Y1|0+0r0#0U0U0e7=0V2R7x0s2K1j6:163z0G0w0v0s0V3$0c0U0$0Z0l0b6Z1j0C3|2`2L6!2f3|0d0K0J5*4d4f8l0p0b8l0B0d0W0Y0d0J8y8m8l0J8D8D4I8D8t8C0W0i8D0K8w8y8A8F8C8T8E8U8S0J5o4~8I8z8B8V8(8D5c7T8P8$8X8/8W8U8Z8J8n5v5+5y8r8@0x8D0y8u8S0A8D8o5,0G8|8D8~8m8O0K0B1m1o0L898b2M0C7v0R0R0%958{0K0p0k8u2i0/0s0f0.0}0C1.2e4G0N7W0l7 0r0o2M6$0h4}7o000o0+0+5c731:9q4f0E0k0X1A0o2Y1Q3W0.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

.128013nmwgPo,}6]uRa8bsr[vce^-1S9_d(Lxiyk02; 5+l4t/.3)fh{:=é7qp050C0v0R0n0G0P0q0M0u0P0n0q0q0!010R0G0(010406050q0l0c0c0n0r0H040z0g0P0l0|0g0b0M020n0c0(0L0M0m0v160r0%0l0v0q050S13151719110(041x1E051H0S1H1J1E110C0G0t0;0?0^0`0X0G0e0X0P1X0X0R0 050,0p0P0v1S0@0_011W1Y1!1Y0R1*1,1(0R0p0g0C191)0r1F0R0X0;1c0q0(0n0b0`0K011.1U010W0.0v0b1k0v1(292b2g1:2j1,2m0c2o040a0M0f0r0g0(0g0q0G1f1h0*270r0r0v0u2J1x2q0b1F0S252V0R2322240C2s0`1!0b2l2G1(1P1R0=1/2)0G2+0b1 1Q1(0(2O1F2T2V30122a1h2;2h2_0r160P0 0y2S3410332r361:383a0 0K3e2b3g2T2(013l0n3b040U3p2U113s3j0`3v3x0Q3A3r343t3G0 0N3J3C3L3E3u0g393w0 0j3Q3h351T3k3V3m040$3!3D3%3F3)3X040o3-3S3/3U3W3x0A3J1G2~1x2/2Y0C2$3t0u1 2y0)1Q1F2}0v2 3f3 480*4g3i3`0I0 0*0W3 3.2=010d0 0M4s3_4u0b0W0 2j1~2m0u0u0G0B0t3w0v0l0r0q0B0n0(0(0v0/4z4m4u0~040D4Y3$4B0 0b4(3t4#0V0Z3Q0M4?4y4t2h4o040G4r1y3f4^4A374+3J514Z2h0g0 0!0!553#3t0c0G0 0J4-3T4#4;4 3q064@5r564)4`0 2O0R4P4,5o2U5t5f5h045j5B4l5u1:4#0h5d4_1:5g3c4=4@5e3T4{4W4}5O523k545I5D3T59045b5!575Q5F3d5I5V3`5m5T5s5)4n5w0+5z5.5K0`5R045=325P0`5M615E5S5I5q5U68015X0/0v5k5^0 5n306f5{5@4*040t664h6h6a5(6t53040u6x3q5|4u5+5c6B6h0b4E0G4G0n4I4K4M1,4P4R4T4V4X5?6z0 4%6$5#3F5%306I580 0x6b3T646G2U6C5L0 0V5`5s6{6,6v3o6*5/690 5N6M6+3u0 0u746.71016K6?3`6O044F1g6S4J4L4N6X4S4U4W1w7562014#6)677b7m5A7g6h5+6=7a7601647f6y7b4/6 5r7h4{5x607M7A7m6w7k6J0 0O7(6D0t7Q3q7h6A7I7b6^7,1:5+7+7!3M7d6_046/7`7*7_727e3!0S4j4f408b0S431x0R458g2!2W1~202Y0n1+8d431D5J3t2O0c0B0W0n0I0v0B0X0U0 1p1r1t1v0M6p4h1K3g1E0E1-2_0c0p2O0M0C006Z7x0M2F4P0;3w0u0l1,0r4y8a7n6Q7p6T0s0b0k1x8:8$0g8(2L0e0r2b0*0:6V4O4Q8X1-058:5A8|1v0R8X002l0t0G2D1h7h172I0X160R0v0F0 090D090(1W0M0w0b096~5(0n0t2P820`9p259s9u9w9y9A0G0M0!0M090C0W920u0Y0y0O9X0q0%0r0R0Y0N0i0i0Y0K0i9F3J0T4y8O8t9o0r9q9P9v049x9z1W9_5(9f0M8!0P0#0M3U8U8W8Y3V019{1G8P040f8~8.9b49041h9W0U5H8:0h0M0.0M8z1e0M9j9l1g990l0F0M5g0P1!1g0:8Yac0q0Tan118e0+0-0/04.