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

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

69
lượt xem 2
download

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

Bài giảng "Cấu trúc dữ liệu và giải thuật: Đệ quy" trình bày các nội dung: Đệ quy, ví dụ về đệ quy, đệ quy có thể không kết thúc, đệ quy có thể không kết thúc. 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 Cấu trúc dữ liệu và giải thuật: Đệ 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 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
Đệ 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ở