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. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Ngôn ngữ lập trình: Bài 9 - Lê Nguyễn Tuấn ThànhNGÔNNGỮ LẬP TRÌNHBài 9:Đệ QuyGiảng viên: Lê Nguyễn Tuấn ThànhEmail: thanhlnt@tlu.edu.vnBộ Môn Công Nghệ Phần Mềm – Khoa CNTTTrường Đại Học Thủy LợiNỘ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ế đệ quyTìm kiếm nhị phânBà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”2GIỚ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 đếnchính hàm đó C++cho phép đệ quyGiố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ảnChia các tác vụ lớn thành các tác vụ conTác vụ con có thể là phiên bản nhỏ hơn của tác vụgốc!Khi đó gọi là đệ quy4VÍ 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áchTá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 sửdụng5