Bài giảng Kỹ thuật lập trình – Chương 6: Kỹ thuật đệ quy. Chương này gồm có những nội dung chính sau: Mô tả đệ quy, thực hiện tính giai thừa, trạng thái hệ thống khi tính giai thừa, thành phần của mô tả đệ quy, phân loại đệ quy, đệ quy nhị phân, đệ quy phi tuyến, đệ quy tương hỗ, Mời các bạn cùng tham khảo. | om .c ng co Kỹ thuật đệ quy an th o ng du u cu https tailieudientucntt om .c ng co Nhắc lại kỹ thuật Đệ quy an Recursive th o ng du u cu https tailieudientucntt Mô tả đệ quy Recursive om .c ng co Mô tả theo cách phân tích an đối tượng thành nhiều th thành phần mà trong số ng các thành phần có thành o phần mang tính chất của du chính đối tượng được mô u cu tả Mô tả đối tượng thông qua chính nó https tailieudientucntt Ví dụ Mô tả đệ quy tập số tự nhiên N Số 1 là số tự nhiên 1-N . Số tự nhiên bằng số tự nhiên cộng 1. om Mô tả đệ quy cấu trúc danh sách kiểu T .c Cấu trúc rỗng là một danh sách kiểu T. ng Ghép nối một thành phần kiểu T nút kiểu co T với một danh sách kiểu T ta có một an danh sách kiểu T. th ng Mô tả đệ quy cây gia phả o du Gia phả của một người bao gồm người đó và gia phả của cha và gia phả của mẹ u cu https tailieudientucntt Ví dụ Tính giai thừa của n Định nghĩa không đệ quy n om n n n-1 1 .c Định nghĩa đệ quy n 1 nếu n 0 ng n n-1 nếu n gt 0 co an Mã C th ng int factorial int n if n 0 return 1 o du else u return n factorial n - 1 cu https tailieudientucntt Thực hiện tính giai thừa om .c factorial 3 ng n 3 co factorial 2 an n 2 th 3 factorial 2 factorial 1 ng 6 o n 1 du 2 factorial 1 2 factorial 0 u cu 1 factorial 0 n 0 1 return 1 1 https tailieudientucntt Trạng thái hệ thống khi tính giai thừa om .c Stack hệ thống ng co factorial 0 an factorial 1 factorial 1 factorial 1 th factorial 2 factorial 2 factorial 2 factorial 2 factorial 2 ng factorial 3 factorial 3 factorial 3 factorial 3 factorial 3 factorial 3 factorial 3 o t du u Thời gian hệ thống cu Trả về từ Trả về từ Trả về từ Trả về từ Gọi hàm Gọi hàm Gọi hàm Gọi hàm hàm hàm hàm hàm factorial 3 factorial 2 factorial 1 factorial 0 factorial 0 factorial 1 factorial 2 factorial 3 t https tailieudientucntt Thành
