Cấu trúc dữ liệu và giải thuật - Đệ quy (Recursion)

Nội dung text: Cấu trúc dữ liệu và giải thuật - Đệ quy (Recursion)

1. Đệ quy (Recursion) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. Đệ quy • Hàm đệ quy là một hàm được định nghĩa bằng bản thân nó • VD: f(0) = 0 và f(x) = 2f(x - 1) + x2 với x > 0 int f(int x) { if (x == 0) // trường hợp cơ sở return 0; else return 2*f(x-1) + x*x; // lời gọi đệ quy }
3. Ví dụ về đệ quy (tiếp) Định giá hàm f(x) = 2f(x - 1) + x2: f(4) = 2*f(3) + 4*4 f(3) = 2*f(2) + 3*3 f(2) = 2*f(1) + 2*2 f(1) = 2*f(0) + 1*1 Gặp trường hợp f(0) = 0 cơ sở và bắt đầu f(1) = 2*0 + 1*1 = 1 quay lui f(2) = 2*1 + 2*2 = 6 f(3) = 2*6 + 3*3 = 21 f(4) = 2*21 + 4*4 = 58
4. Đệ quy có thể không kết thúc • Điều gì xảy ra nếu ta gọi f(-1) sau khi cài đặt hàm f(x) = 2f(x - 1) + x2 như lúc trước? • Dưới đây là một hàm đệ quy không kết thúc: Điều gì xảy ra khi gọi: - bad(1)? - bad(2)? - bad(3)?
5. Đảm bảo chương trình đệ quy kết thúc Hai quy tắc viết chương trình đệ quy đúng: 1. Định nghĩa trường hợp cơ sở − Đây là nơi đệ quy sẽ kết thúc 2. Lời gọi đệ quy phải có sự tiến triển − Mỗi bước phải hướng dần về phía trường hợp cơ sở