Mô tả thông qua chính đối tượng
Trong **mô tả đệ quy**, một đối tượng được định nghĩa thông qua chính loại đối tượng ấy. Chẳng hạn, một bộ hộp lồng nhau có thể được mô tả: hộp nhỏ nhất không chứa hộp khác; mỗi hộp lớn hơn chứa một bộ hộp cùng kiểu nhưng nhỏ hơn. Mô tả có trường hợp bắt đầu và cách tạo trường hợp tiếp theo.
Không phải mọi sự lặp lại đều là đệ quy. Chép cùng một dòng năm lần là thao tác lặp; chỉ từ việc lặp ấy chưa thể kết luận có mô tả hay lời gọi đệ quy.
Giữ phần đã có rồi thêm một phần mới
Gọi $C(n)$ là số ô của hình vuông $n$ hàng, $n$ cột. Hình một ô cho $C(1)=1$. Để từ hình cạnh $n-1$ ô thành hình cạnh $n$ ô, thêm một hàng và một cột; ô góc chung chỉ tính một lần nên thêm $2n-1$ ô.
Vì thế, với $n\ge2$:
$$C(n)=C(n-1)+2n-1.$$
Ví dụ $C(3)=C(2)+5=4+5=9$. Công thức dùng lại cùng đại lượng $C$ ở trường hợp nhỏ hơn, giúp mô tả cả quá trình mà không liệt kê từng hình.
Bài luyện
Đã biết $C(3)=9$ và $C(n)=C(n-1)+2n-1$. Giá trị $C(4)$ là bao nhiêu?
Thêm 2×4−1=7 ô vào 9 ô đã có.
14 chưa đúng với phép cộng 9+7.
18 là cộng hai lần9, khác quy tắc.
25 là số ô của hình 5×5.
Lời giải
Với $n=4$, phần thêm là $2\times4-1=7$. Do đó $C(4)=C(3)+7=9+7=16$.
Bài luyện
Một chương trình dùng vòng for để in cùng một thông báo năm lần. Chỉ từ mô tả đó, kết luận nào đúng?
Số lần gọi phụ thuộc bài toán và dữ liệu.
Cần xem có mô tả tự tham chiếu hoặc lời gọi đến chính hàm hay không.
Mô tả chưa có lời gọi hàm đến chính nó.
Vòng for và lời gọi đệ quy là các cách điều khiển khác nhau.
Lời giải
Lặp lại một thao tác không đồng nghĩa với đệ quy. Mô tả này chỉ cho biết thông báo được in năm lần bằng vòng for; chưa có căn cứ về lời gọi đến chính hàm.
Đang học