Giả sử A = [1, 3, 7, 9] và K = 10. Cần mấy lần gọi hàm đệ quy?
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?
Giải Chuyên đề Tin 11 Bài 2: Thiết kế thuật toán đệ quy - Kết nối tri thức
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.
Lời giải bài tập Chuyên đề Tin 11 Bài 2: Thiết kế thuật toán đệ quy hay, chi tiết khác: