Đệ quy 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. Mời các bạn cùng tham khảo Bài giảng Ngôn ngữ lập trình: Đệ quy dưới đây để nắm rõ nội dung chi tiết về đệ quy. | NGÔN NGỮ LẬP TRÌNH Đệ quy 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 1 Đệ quy 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. 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 đó đó là trường hợp suy biến degenerate case . 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 2 Ví dụ Viết hàm tính n n giai thừa 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 3 Ví dụ Viết hàm tính x x mũ n 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 4 Đệ quy Chương trình đệ quy gồm hai phần chính 1. Phần cơ sở Điều kiện thoát khỏi đệ quy điểm dừng 2. 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 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 5 Phương pháp thiết kế một giải thuật đệ quy Phân rã bài toán thành các bài toán nhỏ hơn. Trong đó có ít nhất một nhiệm vụ con là một trường hợp nhỏ hơn của nhiệm vụ cha giống hệt bài toán ban đầu Phân tích cho đến khi bài toán đủ nhỏ để cho ra kết quả đúng gt đó là điểm dừng 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 6 Chú ý Nếu không thiết kế điểm dừng hàm đệ quy đó sẽ trở thành đệ quy vô hạn 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 7 Bài tập Viết hàm đệ quy cho phép in ra các chữ số của một số nguyên dương theo chiều xuôi mỗi chữ số cách nhau một dấu cách VD cho số 57294 thì in ra 5 7 2 9 4 Viết hàm đệ quy cho phép in ra các chữ số của một số nguyên dương theo chiều ngược mỗi chữ số cách nhau một dấu cách VD cho số 57294 thì in ra 4 9 2 7 5 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 8 Bài tập Viết hàm đệ quy tính số Fibonaci thứ n theo công thức f n f n-1 f n-2 với n gt 3 f n 1 với n 1 hoặc n 2 Viết chương trình in ra dãy n số Fibonaci 10 05 2018 Nguyễn Thị Phương Dung - Khoa CNTT - ĐHSPHN 9
