Bài giảng Kỹ thuật lập trình – Chương 6: Kỹ thuật đệ quy

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình – Chương 6: Kỹ thuật đệ quy om .c ng coKỹ thuật đệ quy an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt om .c ng coNhắc lại kỹ thuật Đệ quy anRecursive th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt Mô tả đệ quy Recursive om .c ng coMô tả theo cách phân tích anđối tượng thành nhiều ththành phần mà trong số ngcác thành phần có thành ophần mang tính chất của duchính đối tượng được mô u cutả Mô tả đối tượng thông qua chính nó CuuDuongThanCong.com https://fb.com/tailieudientucnttVí 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 CuuDuongThanCong.com https://fb.com/tailieudientucnttVí 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>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 } CuuDuongThanCong.com https://fb.com/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) ng6 o n=1 du 2*factorial(1) 2 … factorial (0) u cu 1*factorial(0) n=0 ...