1. Learn
    2. /
  2. Cursuri
    3. /
  3. Exersarea întrebărilor de interviu de programare în Python
Connected

exercițiu

Calculează numărul de apeluri ale funcției

Să luăm un exemplu clasic de recursivitate – șirul Fibonacci, format din numere întregi nenegative începând cu 0, în care fiecare element \(F(n)\) este egal cu suma celor două elemente precedente: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Ți se oferă o funcție care returnează un tuplu cu al \(n\)-lea element al șirului și numărul de apeluri la fib() utilizate:

def fib(n):

  if n < 2:
    return (n, 1)

  fib1 = fib(n-1)
  fib2 = fib(n-2)

  return (fib1[0] + fib2[0], fib1[1] + fib2[1] + 1)

Câte apeluri la fib() sunt necesare pentru a calcula al \(15^{lea}\) și al \(20^{lea}\) element al șirului?

Instrucțiuni

50 XP

Răspunsuri posibile