tailieunhanh - Bài giảng Ngôn ngữ lập trình: Bài 9 - Lê Nguyễn Tuấn Thành

Bài giảng "Ngôn ngữ lập trình - Bài 9: Đệ quy" cung cấp cho người học các kiến thức: Đệ quy với hàm void, đệ quy với hàm trả về giá trị, suy nghĩ theo kiểu đệ quy. nội dung chi tiết. | NGÔN NGỮ LẬP TRÌNH Bài 9: Đệ Quy Giảng viên: Lê Nguyễn Tuấn Thành Email: thanhlnt@ Bộ Môn Công Nghệ Phần Mềm – Khoa CNTT Trường Đại Học Thủy Lợi NỘI DUNG Đệ quy với hàm void Đệ quy với hàm trả về giá trị Truy vết lời gọi đệ quy Đệ quy vô hạn (infinite recursion), tràn (overflows) Hàm Power() Suy nghĩ theo kiểu đệ quy Kỹ thuật thiết kế đệ quy Tìm kiếm nhị phân Bài giảng có sử dụng hình vẽ trong cuốn sách “Practical Debugging in C++, A. Ford and T. Teorey, Prentice Hall, 2002” 2 GIỚI THIỆU VỀ ĐỆ QUY (RECURSION) Một hàm gọi chính nó Trong định nghĩa của hàm đó, có lời gọi đến chính hàm đó C++ cho phép đệ quy Giống như phần lớn ngôn ngữ lập trình bậc cao Có thể là một kỹ thuật lập trình hữu ích Có những giới hạn 3 ĐỆ QUY VỚI HÀM VOID Chia để trị (Devide and Conquer) Kỹ thuật thiết kế cơ bản Chia các tác vụ lớn thành các tác vụ con Tác vụ con có thể là phiên bản nhỏ hơn của tác vụ gốc! Khi đó gọi là đệ quy 4 VÍ DỤ ĐỆ QUY VỚI HÀM VOID Xem xét tác vụ sau: Tìm kiếm một giá trị trong danh sách Tác vụ con 1: tìm kiếm nửa đầu của danh sách Tác vụ con 2: tìm kiếm nửa sau của danh sách Các tác vụ con là phiên bản nhỏ hơn của tác vụ gốc! Khi điều này xảy ra, hàm đệ quy có thể được .