Thuật toán đệ quy

Thuật toán đệ quy là gì?

Thuật toán đệ quy là một phương pháp giải quyết vấn đề bằng cách sử dụng phép gọi đệ quy. Đó là phương pháp thiết kế thuật toán dựa trên việc giải quyết vấn đề lớn bằng cách chia nhỏ thành các vấn đề nhỏ hơn, tương tự như một bài toán được giải bằng cách giải các bài toán con.

Thuật toán đệ quy thường được viết bằng cách sử dụng hàm đệ quy, một hàm gọi chính nó trong thân hàm. Trong một số trường hợp, thuật toán đệ quy có thể dễ dàng hiểu và dễ thực hiện hơn so với các phương pháp giải quyết vấn đề khác, nhưng nó có thể tốn nhiều bộ nhớ và thời gian hơn.

Một số ví dụ về thuật toán đệ quy bao gồm thuật toán tìm kiếm nhị phân, thuật toán sắp xếp quicksort, và thuật toán tính giai thừa của một số nguyên dương.

Lịch sử phát triển

Thuật toán đệ quy được sử dụng từ rất lâu trong lịch sử tính toán. Tuy nhiên, ý tưởng của thuật toán đệ quy chưa được hình thành rõ ràng cho đến khi Alan Turing đưa ra khái niệm máy Turing vào năm 1936. Máy Turing là một công cụ tưởng tượng có thể thực hiện các tính toán đệ quy bằng cách sử dụng phép gọi đệ quy.

Sau đó, ý tưởng của thuật toán đệ quy đã được phát triển và ứng dụng trong nhiều lĩnh vực khác nhau, bao gồm khoa học máy tính, toán học, kỹ thuật và khoa học vật lý. Một số người đã đóng góp quan trọng trong sự phát triển của thuật toán đệ quy bao gồm Alonzo Church, Stephen Kleene, John McCarthy, Peter Landin, và John Backus.

Hiện nay, thuật toán đệ quy vẫn được sử dụng rộng rãi trong các ứng dụng thực tế như trong ngành công nghiệp phần mềm, khoa học dữ liệu và trí tuệ nhân tạo. Nhiều ngôn ngữ lập trình hiện đại cũng hỗ trợ việc viết các thuật toán đệ quy, bao gồm Java, Python và C++.

Các bước thực hiện thuật toán đệ quy

Các bước thực hiện thuật toán đệ quy thường bao gồm:

Bước 1. Xác định điều kiện cơ bản: Điều kiện cơ bản là điều kiện để thuật toán đệ quy dừng lại và trả về kết quả. Điều kiện cơ bản thường được xác định ở đầu thuật toán.

Bước 2. Xác định công thức đệ quy: Công thức đệ quy là công thức dùng để tính toán kết quả của vấn đề lớn bằng cách sử dụng các vấn đề nhỏ hơn. Công thức đệ quy thường được xác định trong thân hàm đệ quy.

Bước 3. Gọi lại hàm đệ quy: Khi thực hiện thuật toán, hàm đệ quy sẽ được gọi lại để giải quyết vấn đề nhỏ hơn. Hàm đệ quy này sẽ tiếp tục gọi chính nó cho đến khi đáp ứng được điều kiện cơ bản và trả về kết quả.

Bước 4. Tính toán kết quả: Kết quả của thuật toán sẽ được tính toán bằng cách kết hợp kết quả của các vấn đề nhỏ hơn đã được giải quyết bằng cách sử dụng công thức đệ quy.

Bước 5. Trả về kết quả: Kết quả cuối cùng của thuật toán sẽ được trả về khi đáp ứng được điều kiện cơ bản.

Quá trình thực hiện thuật toán đệ quy sẽ được lặp đi lặp lại cho đến khi thuật toán dừng lại và trả về kết quả.

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

Tính giai thừa của một số nguyên

Một ví dụ đơn giản về thuật toán đệ quy là thuật toán tính giai thừa của một số nguyên dương n. Giai thừa của n được định nghĩa là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng n. Có thể viết công thức đệ quy cho giai thừa như sau:

n! = 1 nếu n = 1 n! = n * (n-1)! nếu n > 1

Trong đó “!” biểu thị cho toán tử tính giai thừa.

Dưới đây là một ví dụ về thuật toán đệ quy tính giai thừa bằng Python:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

Trong đó hàm factorial(n) là một hàm đệ quy tính giai thừa của n. Nếu n = 1, hàm trả về 1, ngược lại, hàm sẽ gọi chính nó với đối số (n-1) và nhân kết quả với n. Ví dụ, factorial(4) sẽ gọi chính nó với đối số 3, 2, và 1 để tính toán kết quả cuối cùng là 24.

Thuật toán tìm kiếm nhị phân sử dụng đệ quy

Python

def binary_search(arr, left, right, x):
    if right >= left:
        mid = left + (right - left) // 2
 
        # Nếu phần tử được tìm thấy ở giữa mảng
        if arr[mid] == x:
            return mid
 
        # Nếu phần tử nhỏ hơn giữa mảng, thực hiện tìm kiếm bên trái
        elif arr[mid] > x:
            return binary_search(arr, left, mid - 1, x)
 
        # Nếu phần tử lớn hơn giữa mảng, thực hiện tìm kiếm bên phải
        else:
            return binary_search(arr, mid + 1, right, x)
 
    else:
        # Nếu phần tử không được tìm thấy trong mảng
        return -1

C++

#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int x)
{
    if (right >= left) {
        int mid = left + (right - left) / 2;
 
        // Nếu phần tử được tìm thấy ở giữa mảng
        if (arr[mid] == x)
            return mid;
 
        // Nếu phần tử nhỏ hơn giữa mảng, thực hiện tìm kiếm bên trái
        if (arr[mid] > x)
            return binarySearch(arr, left, mid - 1, x);
 
        // Nếu phần tử lớn hơn giữa mảng, thực hiện tìm kiếm bên phải
        return binarySearch(arr, mid + 1, right, x);
    }
 
    // Nếu phần tử không được tìm thấy trong mảng
    return -1;
}

int main()
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        cout << "Khong tim thay phan tu " << x << " trong mang";
    else
        cout << "Tim thay phan tu " << x << " tai chi so " << result << endl;
    return 0;
}

Thuật toán sắp xếp nhanh Quicksort sử dụng đệ quy

Python

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quicksort(left) + [pivot] + quicksort(right)

# Kiểm tra thuật toán sắp xếp quicksort
arr = [3, 7, 2, 9, 1, 8, 5, 6, 4]
print("Mảng chưa được sắp xếp:", arr)
arr = quicksort(arr)
print("Mảng đã được sắp xếp:", arr)

C++

#include <iostream>
using namespace std;

void quicksort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }

    int pivot = arr[left];
    int i = left + 1;
    int j = right;

    while (i <= j) {
        while (i <= j && arr[i] < pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[left], arr[j]);

    quicksort(arr, left, j - 1);
    quicksort(arr, j + 1, right);
}

// Kiểm tra thuật toán sắp xếp quicksort
int main() {
    int arr[] = {3, 7, 2, 9, 1, 8, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Mang chua duoc sap xep: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    quicksort(arr, 0, n - 1);

    cout << "Mang da duoc sap xep: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Tổng kết

Thuật toán đệ quy là một phương pháp giải quyết bài toán dựa trên việc phân chia bài toán thành các bài toán con cùng loại và giải quyết chúng theo cùng một phương pháp. Thuật toán đệ quy được áp dụng trong nhiều lĩnh vực như lập trình, toán học, khoa học máy tính, v.v.

Một số ví dụ về thuật toán đệ quy bao gồm: tìm kiếm nhị phân, sắp xếp quicksort, tính giai thừa, tìm đường đi ngắn nhất trong đồ thị, v.v.

Các bước thực hiện thuật toán đệ quy bao gồm: xác định trường hợp cơ bản, tìm quy luật đệ quy, chia bài toán thành các bài toán con, giải quyết các bài toán con bằng cách gọi lại hàm đệ quy và kết hợp kết quả để giải quyết bài toán ban đầu.

Thuật toán đệ quy có thể được cài đặt bằng nhiều ngôn ngữ lập trình như C++, Python, Java, v.v. Khi cài đặt thuật toán đệ quy, cần chú ý đến việc xác định trường hợp cơ bản và điều kiện dừng đệ quy để tránh lặp vô hạn.