Thuật toán đệ quy tuyến tính (Linear recursive algorithm)

Thuật toán đệ quy tuyến tính (Linear recursive algorithm) là một phương pháp tìm kiếm giá trị trong một danh sách đã cho bằng cách sử dụng đệ quy. Quá trình tìm kiếm được thực hiện bằng cách so sánh giá trị cần tìm với từng phần tử trong danh sách theo thứ tự tuyến tính.

Cách thức hoạt động của thuật toán này như sau:

1. Bắt đầu với phần tử đầu tiên trong danh sách.
2. Nếu phần tử được tìm thấy, trả về vị trí của nó trong danh sách.
3. Nếu phần tử không được tìm thấy, di chuyển đến phần tử tiếp theo và lặp lại quá trình trên.
4. Nếu đến cuối danh sách mà không tìm thấy phần tử cần tìm, trả về giá trị -1.

Độ phức tạp của thuật toán đệ quy tuyến tính (Linear recursive algorithm) là O(n), với n là số lượng phần tử trong danh sách. Tuy nhiên, khi danh sách được sắp xếp, thuật toán tìm kiếm này có thể được cải thiện bằng cách sử dụng thuật toán tìm kiếm nhị phân.

Dưới đây là đoạn code Python mẫu để tìm kiếm một phần tử trong danh sách sử dụng thuật toán đệ quy tuyến tính:

def linear_recursive_search(arr, x, i):
    if i >= len(arr):
        return -1
    elif arr[i] == x:
        return i
    else:
        return linear_recursive_search(arr, x, i+1)

Ví dụ: Cho danh sách [64, 25, 12, 22, 11] và tìm kiếm phần tử có giá trị là 22. Sử dụng thuật toán đệ quy tuyến tính, ta có kết quả là 3.

arr = [64, 25, 12, 22, 11]
x = 22
result = linear_recursive_search(arr, x, 0)
print(result) # Kết quả là 3