Chuỗi Fibonacci trong Python sử dụng đầu vào

Ghi nhớ thuật toán đệ quy

Như bạn đã thấy trong đoạn mã trên, hàm Fibonacci tự gọi chính nó nhiều lần với cùng một đầu vào. Thay vì một cuộc gọi mới mỗi lần, bạn có thể lưu trữ kết quả của các cuộc gọi trước đó trong một thứ gì đó giống như bộ nhớ cache. Bạn có thể sử dụng danh sách Python để lưu trữ kết quả của các phép tính trước đó. Kỹ thuật này được gọi là ghi nhớ

Ghi nhớ tăng tốc độ thực thi các hàm đệ quy đắt tiền bằng cách lưu trữ các kết quả đã tính toán trước đó vào bộ đệm. Bằng cách này, khi cùng một đầu vào xảy ra lần nữa, hàm chỉ cần tra cứu kết quả tương ứng và trả về kết quả đó mà không phải chạy lại tính toán. Bạn có thể tham khảo các kết quả này dưới dạng lưu trữ hoặc ghi nhớ

Với tính năng ghi nhớ, bạn chỉ cần duyệt qua cây cuộc gọi có độ sâu n một lần sau khi trở về từ trường hợp cơ sở, khi bạn truy xuất tất cả các giá trị được tính toán trước đó được đánh dấu bằng màu vàng, F(2) và F(3), từ bộ đệm trước đó

Đường màu cam cho biết không có đầu vào nào của hàm Fibonacci được gọi nhiều lần. Điều này làm giảm đáng kể độ phức tạp về thời gian của thuật toán từ hàm mũ O(2n) thành tuyến tính O(n)

Ngay cả đối với các trường hợp cơ bản, bạn có thể thay thế việc gọi F(0) và F(1) bằng cách chỉ truy xuất các giá trị trực tiếp từ bộ đệm tại các chỉ số 0 và 1, vì vậy cuối cùng bạn chỉ gọi hàm sáu lần thay vì mười lăm lần

Đây là bản dịch có thể có của việc tối ưu hóa này sang mã Python

>>>

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Trong ví dụ này, bạn sử dụng từ điển Python để lưu trữ các số Fibonacci đã tính. Ban đầu,

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Nếu không có số Fibonacci cho giá trị hiện tại của

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Khám phá thuật toán lặp

Điều gì sẽ xảy ra nếu bạn thậm chí không phải gọi hàm Fibonacci đệ quy?

Bạn biết rằng hai số đầu tiên trong dãy là 0 và 1 và mỗi số tiếp theo trong dãy là tổng của hai số liền trước nó. Vì vậy, bạn chỉ cần tạo một vòng lặp cộng hai số trước đó,

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Các số màu tím được in đậm trong sơ đồ bên dưới biểu thị các số mới cần được tính toán và thêm vào

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Để tính số Fibonacci tại vị trí

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

 1# fibonacci_class.py
 2
 3class Fibonacci:
 4    def __init__(self):
 5        self.cache = [0, 1]
 6
 7    def __call__(self, n):
 8        # Validate the value of n
 9        if not (isinstance(n, int) and n >= 0):
10            raise ValueError(f'Positive integer number expected, got "{n}"')
11
12        # Check for computed Fibonacci numbers
13        if n < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

Sử dụng đệ quy và lớp Python

Cách tiếp cận đầu tiên của bạn để tạo chuỗi Fibonacci sẽ sử dụng lớp Python và đệ quy. Một lợi thế của việc sử dụng lớp so với hàm đệ quy được ghi nhớ mà bạn đã thấy trước đây là một lớp giữ trạng thái và hành vi (đóng gói) cùng nhau trong cùng một đối tượng. Tuy nhiên, trong ví dụ hàm,

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Dưới đây là mã triển khai giải pháp dựa trên lớp của bạn

 1# fibonacci_class.py
 2
 3class Fibonacci:
 4    def __init__(self):
 5        self.cache = [0, 1]
 6
 7    def __call__(self, n):
 8        # Validate the value of n
 9        if not (isinstance(n, int) and n >= 0):
10            raise ValueError(f'Positive integer number expected, got "{n}"')
11
12        # Check for computed Fibonacci numbers
13        if n < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

Đây là bảng phân tích về những gì đang xảy ra trong mã

• Dòng 3 định nghĩa lớp

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5

• Dòng 4 định nghĩa trình khởi tạo lớp,

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  6. Đó là một phương thức đặc biệt mà bạn có thể sử dụng để khởi tạo các cá thể lớp của mình. Các phương thức đặc biệt đôi khi được gọi là các phương thức dunder, viết tắt của các phương thức gạch dưới kép

• Dòng 5 tạo thuộc tính thể hiện

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7, có nghĩa là bất cứ khi nào bạn tạo một đối tượng

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5, sẽ có một bộ đệm cho nó. Thuộc tính này ban đầu chứa các số đầu tiên trong dãy Fibonacci

• Dòng 7 định nghĩa một phương thức đặc biệt khác,

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  9. Phương pháp này biến các phiên bản của

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5 thành các đối tượng có thể gọi được

• Dòng 9 và 10 xác thực giá trị của

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  8 bằng cách sử dụng câu lệnh có điều kiện. Nếu

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  8 không phải là số nguyên dương, thì phương thức này sẽ tăng

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  83

• Dòng 13 định nghĩa một câu lệnh có điều kiện để kiểm tra các số Fibonacci đã được tính toán và có sẵn trong

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7. Nếu số ở chỉ mục

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  8 đã có trong

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7, thì dòng 14 trả về nó. Mặt khác, dòng 17 tính số và dòng 18 nối nó với

   1# fibonacci_class.py
   2
   3class Fibonacci:
   4    def __init__(self):
   5        self.cache = [0, 1]
   6
   7    def __call__(self, n):
   8        # Validate the value of n
   9        if not (isinstance(n, int) and n >= 0):
  10            raise ValueError(f'Positive integer number expected, got "{n}"')
  11
  12        # Check for computed Fibonacci numbers
  13        if n < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7 để bạn không phải tính lại số đó

• Dòng 20 trả về số Fibonacci được yêu cầu

Để thử mã này, hãy tiếp tục và lưu mã vào

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>>

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Tại đây, bạn tạo rồi gọi một thể hiện của lớp

 1# fibonacci_class.py
 2
 3class Fibonacci:
 4    def __init__(self):
 5        self.cache = [0, 1]
 6
 7    def __call__(self, n):
 8        # Validate the value of n
 9        if not (isinstance(n, int) and n >= 0):
10            raise ValueError(f'Positive integer number expected, got "{n}"')
11
12        # Check for computed Fibonacci numbers
13        if n < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Việc triển khai thuật toán dãy Fibonacci này khá hiệu quả. Khi bạn có một thể hiện của lớp, thuộc tính

 1# fibonacci_class.py
 2
 3class Fibonacci:
 4    def __init__(self):
 5        self.cache = [0, 1]
 6
 7    def __call__(self, n):
 8        # Validate the value of n
 9        if not (isinstance(n, int) and n >= 0):
10            raise ValueError(f'Positive integer number expected, got "{n}"')
11
12        # Check for computed Fibonacci numbers
13        if n < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

Trực quan hóa thuật toán chuỗi Fibonacci đã ghi nhớ

Bạn có thể hiểu một cách hiệu quả cách mỗi cuộc gọi đến hàm Fibonacci đệ quy được xử lý bằng cách sử dụng biểu diễn ngăn xếp cuộc gọi. Cách mỗi cuộc gọi được đẩy vào ngăn xếp và bật ra phản ánh chính xác cách chương trình chạy. Nó chứng minh rõ ràng việc tính toán số lượng lớn sẽ mất nhiều thời gian như thế nào nếu bạn không tối ưu hóa thuật toán

Trong ngăn xếp cuộc gọi, bất cứ khi nào một hàm trả về kết quả, khung ngăn xếp biểu thị lệnh gọi hàm sẽ bật ra khỏi ngăn xếp. Bất cứ khi nào bạn gọi một chức năng, bạn thêm một khung ngăn xếp mới vào đầu ngăn xếp. Nói chung, thao tác này có độ phức tạp không gian là O(n) vì không có nhiều hơn n khung ngăn xếp trên ngăn xếp cuộc gọi tại một thời điểm

Ghi chú. Có một trình chỉnh sửa mã thân thiện với người mới bắt đầu có tên là Thonny cho phép bạn hình dung ngăn xếp cuộc gọi của một hàm đệ quy theo cách đồ họa. Bạn có thể tham khảo Thonny. Trình chỉnh sửa Python thân thiện với người mới bắt đầu để tìm hiểu thêm

Để trực quan hóa thuật toán Fibonacci đệ quy đã ghi nhớ, bạn sẽ sử dụng một tập hợp các sơ đồ biểu thị ngăn xếp cuộc gọi. Số bước được biểu thị bằng nhãn màu xanh lam bên dưới mỗi ngăn xếp cuộc gọi

Giả sử bạn muốn tính F(5). Để làm điều này, bạn đẩy cuộc gọi đầu tiên đến chức năng vào ngăn xếp cuộc gọi

Để tính F(5), bạn phải tính F(4) như được nêu trong quan hệ truy hồi Fibonacci, vì vậy bạn thêm lệnh gọi hàm mới đó vào ngăn xếp

Để tính F(4), bạn phải tính F(3), vì vậy bạn thêm một lệnh gọi hàm khác vào ngăn xếp

Để tính F(3), bạn phải tính F(2), vì vậy bạn thêm một lệnh gọi hàm khác vào ngăn xếp cuộc gọi

Để tính F(2), bạn phải tính F(1), vì vậy bạn thêm nó vào ngăn xếp. Vì F(1) là trường hợp cơ sở, nó trả về ngay lập tức bằng 1 và bạn xóa cuộc gọi này khỏi ngăn xếp

Bây giờ bạn bắt đầu thư giãn các kết quả theo cách đệ quy. F(1) trả lại kết quả cho hàm gọi của nó, F(2). Để tính F(2), bạn cũng cần tính F(0)

Bạn thêm F(0) vào ngăn xếp. Vì F(0) là trường hợp cơ bản nên nó trả về ngay lập tức, cho bạn 0. Bây giờ bạn có thể xóa nó khỏi ngăn xếp cuộc gọi

Kết quả gọi F(0) này được trả về F(2). Bây giờ bạn có những gì bạn cần để tính F(2) và xóa nó khỏi ngăn xếp

Kết quả của F(2) được trả lại cho người gọi nó, F(3). F(3) cũng cần kết quả của F(1) để hoàn thành phép tính của nó, vì vậy bạn thêm nó trở lại ngăn xếp

F(1) là trường hợp cơ sở và giá trị của nó có sẵn trong bộ đệm, vì vậy bạn có thể trả về kết quả ngay lập tức và xóa F(1) khỏi ngăn xếp

Bạn có thể hoàn thành phép tính cho F(3), là 2

Bạn loại bỏ F(3) khỏi ngăn xếp sau khi hoàn thành phép tính của nó và trả lại kết quả cho người gọi nó, F(4). F(4) cũng cần kết quả của F(2) để tính giá trị của nó

Bạn đẩy cuộc gọi đến F(2) vào ngăn xếp. Đây là nơi bộ đệm tiện lợi xuất hiện. Bạn đã tính toán nó trước đó, vì vậy bạn chỉ có thể truy xuất giá trị từ bộ đệm, tránh việc gọi đệ quy để tính lại kết quả của F(2). Bộ đệm trả về 1 và bạn xóa F(2) khỏi ngăn xếp

F(2) được trả lại cho trình gọi của nó và bây giờ F(4) có tất cả những gì nó cần để tính giá trị của nó, đó là 3

Tiếp theo, bạn loại bỏ F(4) khỏi ngăn xếp và trả lại kết quả của nó cho người gọi cuối cùng và ban đầu, F(5)

F(5) bây giờ có kết quả của F(4) và cũng là kết quả của F(3). Bạn đẩy một lệnh gọi F(3) vào ngăn xếp và bộ đệm tiện lợi sẽ hoạt động trở lại. Trước đó bạn đã tính F(3), vì vậy tất cả những gì bạn cần làm là truy xuất nó từ bộ đệm. Không có quy trình đệ quy để tính F(3). Nó trả về 2 và bạn xóa F(3) khỏi ngăn xếp

Bây giờ F(5) có tất cả các giá trị mà nó cần để tính giá trị của chính nó. Bạn nhận được 5 bằng cách thêm 3 và 2, và đó là bước cuối cùng trước khi bạn loại bỏ lệnh gọi F(5) khỏi ngăn xếp. Hành động này kết thúc chuỗi lệnh gọi hàm đệ quy của bạn

Ngăn xếp cuộc gọi hiện đang trống. Bạn đã hoàn thành bước cuối cùng để tính F(5)

Biểu diễn các lệnh gọi hàm đệ quy bằng sơ đồ ngăn xếp cuộc gọi giúp bạn hiểu tất cả công việc diễn ra đằng sau hậu trường. Nó cũng cho phép bạn xem một hàm đệ quy có thể chiếm bao nhiêu tài nguyên

Đặt tất cả các sơ đồ này lại với nhau cho phép bạn hình dung toàn bộ quá trình trông như thế nào

Bạn có thể nhấp vào hình ảnh trên để phóng to các bước riêng lẻ. Nếu bạn không lưu vào bộ đệm các số Fibonacci đã tính toán trước đó, thì một số giai đoạn ngăn xếp trong sơ đồ này sẽ cao hơn nhiều, điều đó có nghĩa là chúng sẽ mất nhiều thời gian hơn để trả về kết quả cho người gọi tương ứng của chúng

Sử dụng Phép lặp và Hàm Python

Ví dụ trong các phần trước triển khai giải pháp đệ quy sử dụng ghi nhớ làm chiến lược tối ưu hóa. Trong phần này, bạn sẽ viết mã một hàm sử dụng phép lặp. Đoạn mã dưới đây triển khai phiên bản lặp lại của thuật toán dãy Fibonacci của bạn

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Bây giờ, thay vì sử dụng đệ quy trong

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

• Dòng 3 định nghĩa

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  7, lấy một số nguyên dương,

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  8, làm đối số

• Dòng 5 và 6 thực hiện xác thực thông thường của

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  8

• Dòng 9 và 10 xử lý các trường hợp cơ sở trong đó

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  8 là 0 hoặc 1

• Dòng 12 định nghĩa hai biến cục bộ,

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  59 và

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  10, đồng thời khởi tạo chúng bằng hai số đầu tiên trong dãy Fibonacci

• Dòng 13 bắt đầu một vòng lặp

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  11 lặp từ

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  12 đến

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  13. Vòng lặp sử dụng dấu gạch dưới (

  >>> cache = {0: 0, 1: 1}
  
  >>> def fibonacci_of(n):
  ..     if n in cache:  # Base case
  ..         return cache[n]
  ..     # Compute and cache the Fibonacci number
  ..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
  ..     return cache[n]
  
  >>> [fibonacci_of(n) for n in range(15)]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
  

  14) cho biến vòng lặp vì nó là biến loại bỏ và bạn sẽ không sử dụng giá trị này trong mã

• Dòng 15 tính toán số Fibonacci tiếp theo trong dãy và ghi nhớ số trước đó

• Dòng 17 trả về số Fibonacci được yêu cầu

Để dùng thử mã này, hãy quay lại phiên tương tác của bạn và chạy mã sau

>>>

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Việc triển khai

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
..     if n in cache:  # Base case
..         return cache[n]
..     # Compute and cache the Fibonacci number
..     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
..     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]