Giả sử A = [1, 3, 7, 9] và K = 10. Nếu áp dụng chương trình trên thì cần mấy lần

Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 2: Thiết kế thuật toán đệ quy

Câu hỏi 2 trang 14 Chuyên đề Tin học 11:Giả sử A = [1, 3, 7, 9] và K = 10. Nếu áp dụng chương trình trên thì cần mấy lần gọi hàm đệ quy?

Lời giải:

Nếu áp dụng chương trình trên thì cần 4 lần gọi hàm đệ quy

lần đầu tiên gọi hàm binarySearch(A, 0, 3, 10), lần này lệnh return sẽ gọi tiếp hàm binarySearch(A, 0, 1, 10) vì A[mid] < K

lần thứ hai gọi hàm binarySearch(A, 0, 1, 10), lần này lệnh return sẽ gọi tiếp hàm binarySearch(A, 1, 1, 10) vì A[mid] < K

lần thứ ba gọi hàm binarySearch(A, 1, 1, 10), lần này lệnh return sẽ gọi tiếp hàm binarySearch(A, 2, 1, 10) vì A[mid] < K

lần thứ tư gọi hàm binarySearch(A, 2, 1, 10), lần này lệnh return sẽ kết thúc hàm và trả về -1 vì left > right.