Khái niệm đệ quy

1.1 Định nghĩa đệ quy và các khái niệm cơ bản của nó.

Đệ quy — là khi cái gì đó tự lặp lại lại và lại. Hãy tưởng tượng bạn có một hướng dẫn, và một phần của hướng dẫn đó nói làm theo chính hướng dẫn đó. Đó giống như bạn đưa ra lệnh để lặp lại chính lệnh đó.

Ví dụ trong cuộc sống thực:

Gương đối diện nhau:

Hãy tưởng tượng bạn đứng giữa hai tấm gương. Bạn thấy ảnh phản chiếu của mình, và trong ảnh phản chiếu bạn cũng thấy ảnh phản chiếu của mình, và cứ thế tiếp tục mãi mãi. Đây là ví dụ về đệ quy, vì mỗi tấm gương thể hiện ảnh phản chiếu của tấm gương khác.

Búp bê Matryoshka:

Matryoshka — là con búp bê mà bên trong có một con búp bê khác, và bên trong con búp bê đó lại có một con búp bê khác, và cứ thế tiếp tục. Khi bạn mở đến con búp bê nhỏ nhất, không còn gì để mở. Điều này giống như trường hợp cơ bản trong đệ quy — lúc cần dừng lại.

Chia pizza:

Hãy tưởng tượng bạn chia một cái pizza làm đôi. Sau đó bạn lấy một nửa và chia nó làm đôi lần nữa, và cứ tiếp tục cho đến khi miếng pizza quá nhỏ để tiếp tục chia. Chia thành phần — là một quá trình đệ quy, và lúc mà bạn không thể chia miếng nhỏ nữa, — đó là trường hợp cơ bản.

Quan trọng! Đệ quy không phải là lặp lại vô tận lệnh, mà là khi chia một vấn đề phức tạp thành các phần nhỏ hơn, cách tiếp cận để giải quyết từng phần này tương tự như giải quyết toàn bộ vấn đề.

Nó hoạt động như thế nào?

Để hiểu đệ quy, bạn cần biết hai khái niệm cơ bản:

• Trường hợp cơ bản: đây là điều kiện mà tại đó đệ quy dừng lại. Ví dụ, trong trường hợp của matryoshka, trường hợp cơ bản là khi bạn mở con búp bê nhỏ nhất và không còn gì bên trong.
• Trường hợp đệ quy: đây là khi bài toán được lặp lại với các phần nhỏ hơn. Trong ví dụ với pizza, bạn chia miếng pizza, sau đó chia một nửa và cứ thế tiếp tục.

Tại sao nó hữu ích?

Đệ quy giúp giải quyết các vấn đề phức tạp bằng cách chia chúng thành các phần nhỏ hơn dễ dàng hơn. Thay vì giải quyết toàn bộ vấn đề cùng lúc, bạn giải quyết nó từng phần một.

Các ví dụ khác trong cuộc sống:

Câu chuyện trong câu chuyện:

Hãy tưởng tượng, nhân vật chính trong câu chuyện kể một câu chuyện khác, và nhân vật trong câu chuyện đó bắt đầu kể một câu chuyện khác nữa. Khi một trong những câu chuyện kết thúc, bạn quay lại câu chuyện trước đó. Trường hợp cơ bản là khi câu chuyện cuối cùng kết thúc.

Ảnh đệ quy:

Bạn vẽ một tam giác lớn, sau đó ở một góc của tam giác đó vẽ tam giác nhỏ hơn, và cứ tiếp tục cho đến khi tam giác quá nhỏ để vẽ. Trường hợp cơ bản là khi tam giác trở nên quá nhỏ để vẽ.

1.2 Trường hợp cơ bản: định nghĩa và ví dụ.

Trường hợp cơ bản — là điều kiện, mà tại đó các lời gọi đệ quy dừng lại và cho phép hàm trả về giá trị cụ thể. Thông thường đó là giải pháp đơn giản nhất và rõ ràng nhất của bài toán, không cần đệ quy thêm nữa.

Ví dụ về trường hợp cơ bản:

Giai thừa của một số:

Giai thừa của số n được ký hiệu là F(n) == 1*2*3*…*n. Cũng rõ ràng rằng F(n) == n* F(n-1).

Trường hợp cơ bản: giai thừa của số 0 hoặc 1 bằng 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Trường hợp cơ bản
    else:
        return n * factorial(n - 1)
        

Dãy Fibonacci:

Dãy Fibonacci – là dãy số: 1, 1, 2, 3, 5, 8, 13, … Trong đó mỗi số tiếp theo là tổng của hai số trước đó. Đối với F(n) == F(n-1) + F(n-2)

Trường hợp cơ bản: hai số đầu tiên của dãy Fibonacci bằng 1, nên số Fibonacci "thứ không" bằng 0. Hoặc F(0) = 0 và F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Trường hợp cơ bản
    elif n == 1:
        return 1  # Trường hợp cơ bản
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Trường hợp đệ quy: định nghĩa và ví dụ

Trường hợp đệ quy — là phần của hàm giải quyết bài toán bằng cách gọi chính nó với các tham số mới, đưa lời giải đến gần hơn với trường hợp cơ bản. Mỗi lời gọi đệ quy giảm hoặc biến đổi bài toán, để cuối cùng đạt được trường hợp cơ bản.

Ví dụ về trường hợp đệ quy:

Giai thừa của một số:

Trường hợp đệ quy: giai thừa của số n bằng n nhân với giai thừa của số n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Trường hợp cơ bản
    else:
        return n * factorial(n - 1)  # Trường hợp đệ quy
        

Dãy Fibonacci:

Trường hợp đệ quy: F(n) bằng tổng của F(n-1) và F(n-2).

def fibonacci(n):
    if n == 0:
        return 0  # Trường hợp cơ bản
    elif n == 1:
        return 1  # Trường hợp cơ bản
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Trường hợp đệ quy
        

1.4 Ví dụ về thuật toán đệ quy

1. Duyệt cây nhị phân:

Ví dụ duyệt theo thứ tự "in-order".

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Ví dụ sử dụng:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Tìm phần tử lớn nhất trong danh sách:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Trường hợp cơ bản
    else:
        max_of_rest = find_max(lst[1:])  # Trường hợp đệ quy
        return max(lst[0], max_of_rest)
        
# Ví dụ sử dụng:
print(find_max([1, 5, 3, 9, 2]))  # Kết quả: 9
        
        

3. Tìm kiếm nhị phân đệ quy:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Trường hợp cơ bản: phần tử không được tìm thấy
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Trường hợp cơ bản: phần tử được tìm thấy
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Trường hợp đệ quy
    else:
        return binary_search(arr, target, left, mid - 1)  # Trường hợp đệ quy 
# Ví dụ sử dụng:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Kết quả: 4