Xem mẫu
NGÔN NGỮ LẬP TRÌNH
Bài 10: ĐỆ QUY
(Chương 13)
Giảng viên: Nguyễn Xuân Hùng
Mobile: 0908 386 366
Email: nguyenxuanhung@wru.vn
Nguyễn Xuân Hùng – Khoa CNTT – Trường Đại học Thủy Lợi
Nội dung
Tìm hiểu về đề quy
Các loại đệ quy
Bài tập
1. Đệ quy (Recursion)
Là một phương pháp lập trình cho phép một hàm có
thể gọi lại chính nó trực tiếp hoặc gián tiếp.
Ví dụ:
void Test()
{
Test();
}
Một chương trình đệ quy hoặc một định nghĩa đệ quy
thì không thể gọi đến chính nó mãi mãi mà phải có
một điểm dừng đến một trường hợp đặc biệt nào đó,
mà ta gọi là trường hợp suy biến (degenerate case).
Ví dụ: Ta định nghĩa n! như sau:
3
n * (n - 1)!
n!
0! 1
1. Đệ quy (Recursion)
Phương pháp thiết kế một giải thuật đệ quy:
Phân tích trường hợp chung : đưa bài toán dưới
dạng bài toán cùng loại nhưng có phạm vi giải
quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến
trường hợp suy biến
4
Tham số hoá bài toán
Tìm trường hợp suy biến
1. Đệ quy (Recursion)
Chương trình đệ quy gồm hai phần chính:
1.
2.
5
Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm
dừng)
Phần đệ quy: Trong phần thân chương trình có
lời gọi đến chính bản thân chương trình với giá
trị mới của tham số nhỏ hơn giá trị ban đầu
nguon tai.lieu . vn
Bài 10: ĐỆ QUY
(Chương 13)
Giảng viên: Nguyễn Xuân Hùng
Mobile: 0908 386 366
Email: nguyenxuanhung@wru.vn
Nguyễn Xuân Hùng – Khoa CNTT – Trường Đại học Thủy Lợi
Nội dung
Tìm hiểu về đề quy
Các loại đệ quy
Bài tập
1. Đệ quy (Recursion)
Là một phương pháp lập trình cho phép một hàm có
thể gọi lại chính nó trực tiếp hoặc gián tiếp.
Ví dụ:
void Test()
{
Test();
}
Một chương trình đệ quy hoặc một định nghĩa đệ quy
thì không thể gọi đến chính nó mãi mãi mà phải có
một điểm dừng đến một trường hợp đặc biệt nào đó,
mà ta gọi là trường hợp suy biến (degenerate case).
Ví dụ: Ta định nghĩa n! như sau:
3
n * (n - 1)!
n!
0! 1
1. Đệ quy (Recursion)
Phương pháp thiết kế một giải thuật đệ quy:
Phân tích trường hợp chung : đưa bài toán dưới
dạng bài toán cùng loại nhưng có phạm vi giải
quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến
trường hợp suy biến
4
Tham số hoá bài toán
Tìm trường hợp suy biến
1. Đệ quy (Recursion)
Chương trình đệ quy gồm hai phần chính:
1.
2.
5
Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm
dừng)
Phần đệ quy: Trong phần thân chương trình có
lời gọi đến chính bản thân chương trình với giá
trị mới của tham số nhỏ hơn giá trị ban đầu