Python - Đệ quy

Đệ quy cho phép một hàm gọi chính nó. Các bước mã cố định được thực thi lặp đi lặp lại cho các giá trị mới. Chúng ta cũng phải thiết lập các tiêu chí để quyết định khi nào cuộc gọi đệ quy kết thúc. Trong ví dụ dưới đây, chúng ta thấy một cách tiếp cận đệ quy đối với tìm kiếm nhị phân. Chúng tôi lấy một danh sách đã sắp xếp và cung cấp phạm vi chỉ mục của nó làm đầu vào cho hàm đệ quy.

Tìm kiếm nhị phân sử dụng Đệ quy

Chúng tôi thực hiện thuật toán tìm kiếm nhị phân bằng python như hình dưới đây. Chúng tôi sử dụng một danh sách có thứ tự các mục và thiết kế một hàm đệ quy để đưa vào danh sách cùng với chỉ mục bắt đầu và kết thúc làm đầu vào. Sau đó, chức năng tìm kiếm nhị phân tự gọi cho đến khi tìm thấy mục được tìm kiếm hoặc kết luận về sự vắng mặt của nó trong danh sách.

def bsearch(list, idx0, idxn, val):

    if (idxn < idx0):
        return None
    else:
        midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value

        if list[midval] > val:
            return bsearch(list, idx0, midval-1,val)
        elif list[midval] < val:
            return bsearch(list, midval+1, idxn, val)
        else:
            return midval

list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

2
None