Oblicz liczbę wywołań funkcji

Rozważmy klasyczny przykład rekurencji – ciąg Fibonacciego, reprezentowany przez nieujemne liczby całkowite zaczynające się od 0, gdzie każdy element \(F(n)\) jest sumą dwóch poprzednich: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Dana jest funkcja, która zwraca krotkę zawierającą \(n\)-ty element ciągu oraz liczbę wywołań fib():

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)

Ile wywołań fib() jest potrzebnych do obliczenia \(15.\) i \(20.\) elementu ciągu?

Możliwe odpowiedzi

Element \(15.\): 3193 wywołania; element \(20.\): 35421 wywołań

Element \(15.\): 1973 wywołania; element \(20.\): 21891 wywołań

Element \(15.\): 3193 wywołania; element \(20.\): 21891 wywołań

Element \(15.\): 35421 wywołań; element \(20.\): 1973 wywołania

ćwiczenie

Oblicz liczbę wywołań funkcji

Instrukcje

Możliwe odpowiedzi

.css-6su6fj{-webkit-flex-shrink:0;-ms-flex-negative:0;flex-shrink:0;}ćwiczenie

Instrukcje

Możliwe odpowiedzi

ćwiczenie