Bài giảng Kỹ thuật lập trình: Đệ quy - Trịnh Tấn Đạt (2024)

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:63

Thêm vào BST

Báo xấu

3
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Kỹ thuật lập trình: Đệ quy" cung cấp cho người đọc các nội dung: Khái niệm, phân loại, các vấn đề đệ quy thông dụng, đệ quy và chia để trị, bài toán tháp Hà Nội, đệ quy và quy lui (option), bài toán Edit distance (option), bài toán Closet pairs of points (option), bài tập. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình: Đệ quy - Trịnh Tấn Đạt (2024)

Đệ Quy (Recursion) Trịnh Tấn Đạt Khoa CNTT - Đại Học Sài Gòn Email: trinhtandat@sgu.edu.vn Website: https://sites.google.com/site/ttdat88/
Nội dung ▪ Khái niệm ▪ Phân loại ▪ Các vấn đề đệ quy thông dụng ▪ Đệ quy và chia để trị ▪ Bài toán tháp hà nội ▪ Đệ quy và quy lui (option) ▪ Bài toán Edit distance (option) ▪ Bài toán Closet pairs of points (option) ▪ Bài Tập
Đệ Quy ▪ Đệ quy là kỹ thuật đưa bài toán hiện tại về một bài toán cùng loại, cùng tính chất (đồng dạng) nhưng ở cấp độ thấp hơn. Quá trình này tiếp tục cho đến khi bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ cấp độ này ta lần ngược lại để giải các bài toán ở cấp độ cao hơn cho đến khi giải xong bài toán ban đầu. ▪ Ví dụ: Định nghĩa n giai thừa: n! = 1*2*3*4*5*…*n → định nghĩa tự nhiên n*(n-1)! với 0!=1 → định nghĩa bằng đệ quy
Đệ Quy
Các ứng dụng ▪ Hình học fractal ▪ Game candy crush ▪ Structure “Tree” ▪ … Koch snowflake Candy Crush
Đệ Quy - Khái niệm ▪ Kỹ thuật đệ quy: là kỹ thuật định nghĩa một khái niệm có sử dụng chính khái niệm đang cần định nghĩa. ▪ Hàm đệ quy: là hàm mà trong thân của nó có lệnh gọi lại chính nó dành cho đối tượng ở cấp thấp hơn. ▪ Ví dụ: Hàm tính n! … Hàm(…) { … … Lời gọi Hàm … … … }
Đệ quy S = 1+2+3+…+n ▪ Hai yếu tố cần để tiến hành một phương thức đệ quy là: o Có điều kiện dừng (phần cơ sở, phần neo): Xác định quy luật của phương thức và tìm giá trị cụ thể khi thỏa mãn một điều kiện nhất định. Nếu hàm đệ quy không có phần này thì hàm sẽ bị lặp vô hạn và sinh lỗi khi thực hiện. o Phương thức đệ quy: Phương thức đệ quy sẽ gọi lại chính nó nhưng dành cho cấp độ thấp hơn. cho đến khi nó trả về điều kiện dừng ở bước 1.
Ví dụ Tính giai thừa n! #include using namespace std; int factorial(int n) { if (n == 1) //phần neo Vòng lặp vô tận return 1; else #include return (n * factorial(n - 1)); // phần đệ quy using namespace std; } int main() { void p() { cout
Đệ Quy ❖ Cách viết hàm đệ quy ▪ Định nghĩa tác vụ đệ quy thế nào thì viết hàm đệ quy như vậy. Xét 2 trường hợp neo (thực hiện không đệ quy) và trường hợp đệ quy. ▪ Ví dụ: Chuyển các định nghĩa sau về dạng đệ quy: S(n) = 1+2 +3+… + n S(n) = 1+1/2 + 1/3 + ... + 1/n S(n) = 1*2 + 2*3+ 3*4 + 4*5 +.….+ n(n+1)
Bài toán dãy số Fibonacci ▪ Fibonacci (1180 - 1250) được biết đến nhiều nhất với dãy số mang tên ông - dãy số Fibonacci. ▪ Dãy số này xuất hiện trong bài toán dưới đây viết trong cuốn Liber Abaci: "Trong một năm, bắt đầu chỉ từ một đôi thỏ, bao nhiêu đôi thỏ sẽ được sinh ra nếu mỗi tháng một đôi thỏ sinh được một đôi thỏ con và cặp thỏ này lại đẻ được từ tháng thứ hai trở đi?“ ▪ Dãy số Fibonacci có nguồn gốc từ bài toán trên là một dãy sao cho mỗi số hạng, kể từ sau số hạng thứ nhất, bằng tổng của hai số đứng ngay trước nó. Dãy số đó là: 1,1,2,3,5,8,13,21,34,55,89,144....
Bài toán dãy số Fibonacci ▪ Dãy số Fibonacci: F(n)= F(n-1)+F(n-2) (phần đệ quy) F(n)=1 với n
Bài tập Viết hàm đệ quy cho các bài toán
Bài tập Viết hàm đệ quy cho các bài toán
Đệ Quy ❖ Phân loại đệ quy (chỉ là hình thức) ▪ Đệ quy tuyến tính: trong thân hàm có duy nhất một lời gọi hàm gọi lại chính nó một cách tường minh. ▪ Đệ quy nhị phân: Trong thân hàm có hai lời gọi hàm gọi lại chính nó một cách tường minh. ▪ Đệ quy lồng: Tham số trong lời gọi hàm là một lời gọi đệ quy. ▪ Đệ quy hỗ tương: Trong thân hàm này có lời gọi hàm tới hàm kia và bên trong thân hàm kia có lời gọi hàm tới hàm này ▪ Đệ quy phi tuyến: Trong thân hàm có lời gọi hàm lại chính nó được đặt bên trong thân vòng lặp.
Đệ quy tuyến tính ▪ Đệ quy tuyến tính: bên trong thân hàm chỉ gọi hàm đệ quy 1 lần ▪ Cấu trúc hàm dạng đệ quy tuyến tính
Đệ quy nhị phân ▪ Đệ quy nhị phân: bên trong thân hàm gọi hàm đệ quy 2 lần. ▪ Cấu trúc hàm dạng đệ quy nhị phân
Đệ quy lồng ▪ Hàm được gọi là đệ quy lồng nếu tham số trong lời gọi hàm là một lời gọi đệ quy. ▪ Cấu trúc hàm dạng đệ qui lồng
Đệ quy hỗ tương ▪ Trong đệ quy tương hỗ thì thường có 2 hàm, và trong thân của hàm này có lời gọi của hàm kia , điều kiện dừng và giá tri trả về của cả hai hàm có thể giống nhau hoặc khác nhau. Cấu trúc hàm dạng đệ quy Hàm nguyên mẫu (Function Prototype)
Function Prototype ▪ Hàm nguyên mẫu cung cấp cho trình biên dịch (compiler) tên của hàm, kiểu dữ liệu mà hàm trả về, số lượng các đối số mà hàm cần cung cấp, kiểu dữ liệu và thứ tự của các đối số đó. ▪ Hàm nguyên mẫu giúp cho trình biên dịch xác nhận các lời gọi hàm mà chưa cần định nghĩa hàm đó.
Đệ quy phi tuyến ▪ Đệ quy phi tuyến: nếu bên trong thân hàm có lời gọi lại chính nó được đặt bên trong thân của vòng lặp. ▪ Cấu trúc hàm dạng đệ quy phi tuyến