Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Đệ quy - Nguyễn Mạnh Hiển

Đệ quy (Recursion) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn Đệ 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 } 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 f(0) = 0 f(1) = 2*0 + 1*1 = 1 f(2) = 2*1 + 2*2 = 6 f(3) = 2*6 + 3*3 = 21 f(4) = 2*21 + 4*4 = 58 Gặp trường hợp cơ sở và bắt đầu quay lui Đệ 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)? Đả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ở