Tính số lần gọi hàm

Hãy xét một ví dụ kinh điển về đệ quy – dãy Fibonacci, gồm các số nguyên không âm bắt đầu từ 0, trong đó mỗi phần tử \(F(n)\) bằng tổng của hai phần tử liền trước: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Bạn được cho một hàm trả về một bộ giá trị (tuple) gồm phần tử thứ \(n\) của dãy và số lần gọi fib() đã dùng:

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ần bao nhiêu lần gọi fib() để tính các phần tử thứ \(15^{th}\) và \(20^{th}\) của dãy?

Các phương án trả lời

Phần tử \(15^{th}\): 3193 lần gọi; phần tử \(20^{th}\): 35421 lần gọi

Phần tử \(15^{th}\): 1973 lần gọi; phần tử \(20^{th}\): 21891 lần gọi

Phần tử \(15^{th}\): 3193 lần gọi; phần tử \(20^{th}\): 21891 lần gọi

Phần tử \(15^{th}\): 35421 lần gọi; phần tử \(20^{th}\): 1973 lần gọi

Bài tập

Tính số lần gọi hàm

Hướng dẫn

Các phương án trả lời

.css-6su6fj{-webkit-flex-shrink:0;-ms-flex-negative:0;flex-shrink:0;}Bài tập

Hướng dẫn

Các phương án trả lời

Bài tập