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

.12801354)2R,%Ba- iVèà8m16Cl.e:9A;S/dktf+r?3sogu0Ppnh=cLéyvêz(wq_b050E0x0G0j0m0v0M0l0W0v0j0M0M0V010G0m0S010406050M0P0r0r0j0J0Z040C0N0v0P0 0N0T0l020j0r0S0B0l0f0x190J0)0P0x0M050D16181a1c140S041A1H051K0D1K1M1H140E0m0!0@0_0{0}0U0m0O0U0v1!0U0G12050/0+0v0x1V0`0|011Z1#1%1#0G1-1/1+0G0+0N0E1c1,0J1I0G0U0@1f0M0S0j0T0}0e011;1X010H0;0x0T1n0x1+2c2e2j1?2m1/2p0r2r040a0l0R0J0N0S0N0M0m1i1k0-2a0J0J0x0W2M1A2t0T1I0D282Y0G2625270E2v0}1%0T2o2J1+1S1U0^1=2,0m2.0T221T1+0S2R1I2W2Y33152d1k2@2k2|0J190v120s2V3713362u391?3b3d120e3h2e3j2W2+013o0j3e040L3s2X143v3m0}3y3A0c3D3u373w3J120b3M1J311A2=2#0E2)3w0W222B0,1T1I300x323i3T3$0-3.3l1W1?0F120-0H3T3G3^0}0(120l3~3O3H3x0H122m212p0W0W0m453@2^0111040%4h38403x120T4o3w4l0d0y3M060l4B443 4j3`040m3}1B3i4D464q0T4s3M4M4i2k0N12020v0G0B4R3k4p4j0r0m3q4u474l4y4K3t4A4C4?4$3w4G2R0G0P0J4t4:2X4S4%3a4Q50134@4E2k4G0x0=0x4,4q4.4z4?584N4F124{4}4 33523P4a0m4c0j4e4g564^4-124n5A593n555r5B4q4V040k4#5G0}4)3f5f4j4w5P5l4U120I5X4T5H044b1j5x4f5U2k4l5E355Q4r045q4L5K4j5M5O565s475S043r5F5Y1?5W56140D3;3-3U6d0D3X1A0G3Z6i2%2Z21232#0j1.6f3X1G3?531?2R0r0*0H0j0F0x0*0U0L121s1u1w1y0l4/351N3j1H0X0j0l0H1j2T0m1j0l300Y0W0Y0-0T0G1:0-0!0m2o0G0l2$0o0?2y6-0l0p6$1a0 0J0l2O056c5^0l0V0l0L3S6b3%040l2o6:2G0T0g0@1a0l1/0?0r0#2A0?0W3z0W0P0=0l0M1j6?0J0Y0S0Y0G0Y0?2O6^0?2|0r0+2R0P0M6N6X0m0M0w446R6v056V0U2R0H1Y1|0S0M0y0D0D0(7=0w2R7x0J2K1j6:163z0m0$0x0J0w3$0r0D0K0H0P0T6Z1j0*3|2`2L6!2f3|0h0e0Q5*4d4f8l0q0T8l0z0h0L0A0h0Q8y8m8l0Q8D8D4I8D8t8C0L0u8D0e8w8y8A8F8C8T8E8U8S0Q5o4~8I8z8B8V8(8D5c7T8P8$8X8/8W8U8Z8J8n5v5+5y8r8@0k8D0s8u8S0i8D8o5,0m8|8D8~8m8O0e0z1m1o0B898b2M0*7v0v0v0V958{0e0q0t8u2i0/0J0O0.0}0*1.2e4G0n7W0P7 0M0j2M6$0N4}7o000j0S0S5c731:9q4f0%0t0d1A0j2Y1Q3W0.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

.1280135[4})2R,a- i8m16l7.e:9;S/dktf{+r3sogu0x]Ppnh=cLéyv^(wq_b050A0u0C0j0m0r0I0l0U0r0j0I0I0T010C0m0Q010406050I0L0o0o0j0G0X040y0J0r0L0|0J0R0l020j0o0Q0x0l0h0u160G0$0L0u0I050z13151719110Q041x1E051H0z1H1J1E110A0m0Y0;0?0^0`0S0m0K0S0r1X0S0C0 050,0(0r0u1S0@0_011W1Y1!1Y0C1*1,1(0C0(0J0A191)0G1F0C0S0;1c0I0Q0j0R0`0g011.1U010D0.0u0R1k0u1(292b2g1:2j1,2m0o2o040a0l0P0G0J0Q0J0I0m1f1h0*270G0G0u0U2J1x2q0R1F0z252V0C2322240A2s0`1!0R2l2G1(1P1R0=1/2)0m2+0R1 1Q1(0Q2O1F2T2V30122a1h2;2h2_0G160r0 0p2S3410332r361:383a0 0g3e2b3g2T2(013l0j3b040H3p2U113s3j0`3v3x0d3A3r343t3G0 0b3J3C3L3E3u0J393w0 0q3Q3h351T3k3V3m040s3!3D3%3F3)3X040n3-3S3/3U3W3x0w3J1G2~1x2/2Y0A2$3t0U1 2y0)1Q1F2}0u2 3f3 480*4g3i3`0B0 0*0D3 3.2=010#0 0l4s3_4u0R0D0 2j1~2m0U0U0m0%0Y3w0u0L0G0I0%0j0Q0Q0u0/4z4m4u0~040!4Y3$4B0 0R4(3t4#0f0v3Q0l4?4y4t2h4o040m4r1y3f4^4A374+3J514Z2h0J0 0T0T553#3t0o0m0 0M4-3T4#4;4 3q064@5r564)4`0 2O0C4P4,5o2U5t5f5h045j5B4l5u1:4#0i5d4_1:5g3c4=4@5e3T4{4W4}5O523k545I5D3T59045b5!575Q5F3d5I5V3`5m5T5s5)4n5w0+5z5.5K0`5R045=325P0`5M615E5S5I5q5U68015X0/0u5k5^0 5n306f5{5@4*040Y664h6h6a5(6t53040U6x3q5|4u5+5c6B6h0R4E0m4G0j4I4K4M1,4P4R4T4V4X5?6z0 4%6$5#3F5%306I580 0k6b3T646G2U6C5L0 0f5`5s6{6,6v3o6*5/690 5N6M6+3u0 0U746.71016K6?3`6O044F1g6S4J4L4N6X4S4U4W1w7562014#6)677b7m5A7g6h5+6=7a7601647f6y7b4/6 5r7h4{5x607M7A7m6w7k6J0 0F7(6D0Y7Q3q7h6A7I7b6^7,1:5+7+7!3M7d6_046/7`7*7_727e3!0z4j4f408b0z431x0C458g2!2W1~202Y0j1+8d431D5J3t2O0o0%0D0j0B0u0%0S0H0 1p1r1t1v0l6p4h1K3g1E0V1-2_0o0(2O0l0A006Z7x0l2F4P0;3w0U0L1,0G4y8a7n6Q7p6T0c0R0O1x8:8$0J8(2L0K0G2b0*0:6V4O4Q8X1-058:5A8|1v0C8X002l0Y0m2D1h7h172I0S160C0u0N0 090!090Q1W0l0Z0R096~5(0j0Y2P820`9p259s9u9w9y9A0m0l0T0l090A0D920U0E0p0F9X0I0$0G0C0E0b0e0e0E0g0e9F3J0t4y8O8t9o0G9q9P9v049x9z1W9_5(9f0l8!0r0W0l3U8U8W8Y3V019{1G8P040P8~8.9b49041h9W0H5H8:0i0l0.0l8z1e0l9j9l1g990L0N0l5g0r1!1g0:8Yac0I0tan118e0+0-0/04.