Bài giảng Kỹ thuật lập trình: Đệ quy - Nguyễn Minh Huy

Bài giảng Kỹ thuật lập trình: Đệ quy, được biên soạn gồm các nội dung chính sau Tổng quan về đệ quy; Phân loại đệ quy; Các vấn đề đệ quy thông dụng. 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: Đệ quy - Nguyễn Minh HuyĐệ quy GV. Nguyễn Minh HuyKỹ thuật lập trình - Nguyễn Minh Huy 1Nội dung Tổng quan về đệ quy. quy. Phân loại đệ quy. quy. Các vấn đề đệ quy thông dụng. dụng.Kỹ thuật lập trình - Nguyễn Minh Huy 2Nội dung Tổng quan về đệ quy. quy. Phân loại đệ quy. quy. Các vấn đề đệ quy thông dụng. dụng.Kỹ thuật lập trình - Nguyễn Minh Huy 3Tổng quan về đệ quy Khái niệm đệ quy: quy: Đệ quy là gì? gì? Xem phần…”Đệ quy là gì?”!! phần…”Đệ gì?”!! Đệ quy là… là… Định nghĩa một vấn đề bằng chính vấn đề đó!! đó!! Một vài định nghĩa đệ quy: quy: n! = n * (n – 1)!. f(n) = f(n – 1) + f(n – 2). n là số tự nhiên nếu n – 1 cũng là số tự nhiên N. Tổ tiên của A là những người sinh ra…tổ tiên của A. ra…Kỹ thuật lập trình - Nguyễn Minh Huy 4Tổng quan về đệ quy Khái niệm đệ quy: quy: Cấu trúc một định nghĩa đệ quy: quy: Phần dừng: trường hợp cơ bản. dừng: bản. Phần đệ quy: suy biến vấn đề về trường hợp đơn giản hơn. quy: hơn. - 0! = 1 - n! = n * (n – 1)!. - f(0) = 0 - f(1) = 1 - f(n) = f(n – 1) + f(n – 2). - 0 là số tự nhiên nhỏ nhất. nhất. - n là số tự nhiên nếu n – 1 là số tự nhiên. nhiên. - Người trực tiếp sinh ra A là tổ tiên của A. - Người sinh ra tổ tiên của A là tổ tiên của A.Kỹ thuật lập trình - Nguyễn Minh Huy 5Tổng quan về đệ quy Đệ quy trong lập trình: trình: Hàm đệ quy: quy: Thân hàm có lời gọi hàm lại chính nó. nó. Lời gọi hàm trức tiếp hay gián tiếp. tiếp. // Đệ quy trực tiếp. tiếp. // Đệ quy gián tiếp. tiếp. void func() func() void func1() func1() { { // … // … func(); func(); func2(); // … // … } } void func2() func2() { // … func1(); // … }Kỹ thuật lập trình - Nguyễn Minh Huy 6Tổng quan về đệ quy Đệ quy trong lập trình: trình: Cấu trúc hàm đệ quy: quy: ( [Danh sách tham số] ) về> hàm> [Danh số] { if () () // Xử lý trường hợp cơ bản. bản. else // Gọi lại hàm đệ quy. quy. } int tinhGT(int n) tinhGT( int fibo(int n) fibo( { { if (n == 0) (n 0) if (n == 0) (n 0) return 1; return 0; return n * tinhGT(n – 1); tinhGT(n 1); if (n == 1) (n 1) } return 1; return fibo(n – 1) + fibo(n – 2); fibo(n fibo(n 2); }Kỹ thuật lập trình - Nguyễn Minh Huy 7Tổng quan về đệ quy Đệ quy trong lập trình: trình: Kiểu dữ liệu đệ quy: ...