Giải chuyên đề Tin 11 Cánh diều Bài 2. Thuật toán đệ quy có đáp án

Mô tả đệ quy cho hàm F(n) để tính a$^{n}$ như sau:

{Hàm_đệ_quy} ({Danh_sách_tham_số})

{

{Gọi_lại_hàm_đệ_quy}({Danh_sách_tham_số});

}

a) Cho biết kết quả thu được của hai chương trình khi giá trị của cặp (4, n) nhập vào lần lượt bằng (2, 4) và (3, 6).

print (z, "mũ", n, "=", power1(2,4))

print (z, "mũ", n, "=", power1(3,6))

b) Nhận xét

Các ngôn ngữ lập trình bậc cao thường cho phép xây dựng các hàm đệ quy, nghĩa là trong thân của bàm có chứa những câu lệnh gọi đến chính nó

a) Chương trình ở Hình 3: dấu ? trong hàm h(n) cần được thay như sau để tính được số lượng cái bắt tay diễn ra trong phòng họp có n người:

return 1

else

return h(n-1) + 1 // Gọi đệ quy

a) return 1

else

return F (n - 1)

b) Ý nghĩa của I7 bước đã cho.

Trong hàm có một hoặc nhiều lệnh gọi đến chính nó.

Mỗi lần gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn so với lần gọi trước. Khi đạt được trường hợp cơ sở thì chương trình không cần gọi đệ quy.

Thuật toán đệ quy được cài đặt dưới dạng hàm đệ quy, để xử lí với các đối tượng được định nghĩa đệ quy.

a) return 1

else

return F (n - 1)

b) Ý nghĩa của I7 bước đã cho.

Trong hàm có một hoặc nhiều lệnh gọi đến chính nó.

Mỗi lần gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn so với lần gọi trước. Khi đạt được trường hợp cơ sở thì chương trình không cần gọi đệ quy.

Thuật toán đệ quy được cài đặt dưới dạng hàm đệ quy, để xử lí với các đối tượng được định nghĩa đệ quy.

Hàm đệ quy in_loi_bai_hat (n) với n là số kẹo để có thể in ra lời bài hát như trên nếu gọi hàm in loi bai hat(20):

{Hàm_đệ_quy} ({Danh_sách_tham_số})

{

{Gọi_lại_hàm_đệ_quy}({Danh_sách_tham_số});

}

Những câu sau đây đúng khi nói về hàm đệ quy:

c) Hàm đệ quy là hàm mà thân hàm có chứa những lệnh gọi đến chính nó.

đ) Hàm đệ quy được sử dụng để cài đặt thuật toán đệ quy.

g) Hàm đệ quy không bao giờ dừng nếu không có trường hợp cơ sở.