TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 5: Đệ quy

Bài giảng "Cấu trúc dữ liệu và giải thuật trong C++ - Bài 5: Đệ quy" cung cấp cho người học các kiến thức: Đệ qui trong thực tế, hàm (phương thức) đệ qui, đệ qui tuyến tính – Đệ qui 1 lần, cách tính số mũ,. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 5: Đệ quy Bài 5. Đệ qui (Recursion) Đệ qui trong lập trình 1 Đệ qui trong thực tế (Recursion in practice) Hệ điều hành: Các thư mục Cú pháp của ngôn ngữ lập trình (Syntax of languages) Đồ họa máy tính (Computer Graphics) Tự nhiên: cây cối Đệ qui trong lập trình 2 Một cuộc hành trình 1000 bước và việc thực hiện hành trình bắt đầu ở bước thứ nhất. Làm thế nào thế nào để hoàn thành cuộc hành trình này? Thực hiện bước 1 và tạo ra cuộc hành trình mới có 999 bước. Đệ qui trong lập trình 3 Hàm (phương thức) đệ qui Đệ qui: Khi một hàm gọi đến chính nó Ví dụ tính giai thừa: n! = 1· 2· 3· ··· · (n-1)· n 1 if n 0 f ( n) n f ( n 1) else Hàm trong C++ // hàm đệ qui tính giai thừa int recursiveFactorial(int n) { if (n == 0) return 1; // trường hợp cơ sở else return n * recursiveFactorial(n- 1); } Đệ qui trong lập trình 4 Đệ qui tuyến tính – Đệ qui 1 lần Kiểm tra trường hợp cơ sở. Bắt đầu bằng việc kiểm tra các trường hợp cơ sở ( ở đó phải có ít nhất một trường hợp). Đây chính là điều kiện để kết thúc đệ qui. Các lời gọi đệ qui hàm phải thực sự hướng quá trình đệ qui về trường hợp cơ sở (để kết thúc đệ qui). Đệ qui một lần. Thực hiện gọi đệ qui chỉ một lần trong hàm. (Có thể trong hàm có nhiều bước kiểm tra để quyết định lựa chọn lời gọi đệ qui, nhưng trong tất cả các trường hợp đó thì chỉ một trường hợp được gọi thực sự) Khi định nghĩa hàm đệ qui thì mỗi lần gọi đệ qui trong hàm phải dẫn dần về trường hợp cơ sở. Đệ qui trong lập trình 5 Ví dụ 1:Cộng các phần tử của một mảng Cho mảng A có n phần tử 4 3 6 2 5 Đệ qui trong lập trình 6 Ví dụ đơn giản cho đệ qui tuyến tính Algorithm LinearSum(A, n): Ví dụ vết đệ qui: Input: call return 15 + A[4] = 15 + 5 = 20 Một mảng A có kiểu nguyên và số LinearSum(A,5) nguyên n ≥ 1, A có ít nhất n phần tử call return 13 + A[3] = 13 + 2 = .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.