Tóm tắt lý thuyết Tin học cơ sở về "Đệ quy" | Học viện Công nghệ Bưu chính Viễn thông

lOMoARcPSD|37922327 lOMoARcPSD|37922327 Đệ quy
Một hàm đệ quy l một h m gọi lại ch nh n trực tiếp hoặc giÁn
tiếp th ng qua cÁc h m khÁc.
Đy l một chủ đề phức tạp sẽ được thảo luận v ứng dụng cụ thể hơn
trong loạt b i về cấu trœc dữ liệu v giải thuật. Trong nội dung n y ta sẽ:
- tiếp cận với khÁi niệm v
- những v dụ cơ bản nhất về đệ quy.
Hàm đệ quy thường dùng để giải quyết các bài toán có cùng
đặc điểm chung.Trong lời gọi đệ quy, hàm đệ quy thường tự biết
xử l trường hợp cơ bản nhất gọi là trường hợp cơ sở/ điểm dừng.
Nếu h m đệ quy được gọi với vấn đề ở trường hợp cơ sở, n trả về
kết quả. Nếu hàm đệ quy được gọi với vấn đề ở trường hợp phức
tạp hơn, n chia vấn đề th nh 2 phần: một phần n biết cÁch xử l ,
v phần c n lại n kh ng biết cÁch xử lý. Để c thể đệ quy, vấn đề
mà nó chưa biết giải quyết sẽ tr ng giống với vấn đề gốc ban đầu
nhưng nhỏ hơn, tức đỡ phức tạp hơn. Do vấn đề nhỏ hơn này giống
y như vấn đề mà hàm đang xử lý nên hàm đệ quy tiếp tục gọi đệ
quy với bản sao của h m hiện tại để giải quyết vấn đề đang được
n i tới. Hàm đệ quy thường đi kèm với keyword return v kết quả
của lời gọi h m l sự kết hợp của phần vấn để m h m biết cÁch xử
l v phần vấn đề h m chưa biết cÁch xử lý đề tạo th nh kết quả
trả về cho nơi gọi h m. Vấn đề cứ được chia nhỏ ra tới khi h m
gặp trường hợp cơ sở, lœc n y h m sẽ lần lượt trả về kết quả
theo chiều ngược lại của lời gọi h m.
V dụ t nh 5! bằng đệ quy (h nh ảnh lấy trong t i liệu deitel-c trang 189). lOMoARcPSD|37922327
Thể hiện bằng chương trình: lOMoARcPSD|37922327 Kết quả thực hiện:
H nh sau minh họa việc giải quyết vấn đề t m số fibonacy thứ n. (cøng t i liệu trang 193). lOMoARcPSD|37922327 Chương trình: Kết quả thực hiện: lOMoARcPSD|37922327
So sÁnh đệ quy v v ng lặp:
Đệ quy v v ng lặp c một số điểm chung và riêng như sau:
- Cøng dựa trŒn cấu trúc điều khiển: v ng lặp dựa trŒn cấu
trœc điều khiển lặp, còn đệ quy dựa trŒn cấu trœc điều khiển lựa chọn.
- Cả v ng lặp và đệ quy dựa trŒn việc thực hiện lặp lại cøng
một c ng việc giống nhau, điều này ta đã thấy rı r ng trong
v ng lặp, với đệ quy th n lặp lại việc gọi hàm để tiến h nh
thực hiện tiếp vấn đề con của vấn đề hiện tại.
- Cả v ng lặp và đê quy đều có điều kiện kết thœc việc thực
hiện lặp đi lặp lại: v ng lặp kết thœc lặp khi điều kiện lặp kh ng lOMoARcPSD|37922327
c n thỏa mãn. Còn hàm đệ quy kết thœc lặp việc gọi đệ quy khi
gặp trường hợp cơ sở hay c n gọi là điểm dừng.
- Cả hai đều c thể lặp v hạn: v ng lặp lặp v hạn nếu điều kiện
lặp luôn đúng, đệ quy lặp v hạn nếu vấn đề kh ng nhỏ hơn sau
mỗi lần đệ quy, kết quả là điều kiện dừng kh ng bao giờ được t m thấy.
- Với đệ quy, sau mỗi lần gọi đệ quy, vấn đề sẽ nhỏ dần. Với v
ng lặp, vấn đề không thay đổi sau mỗi lần lặp.
- Đệ quy thường tiŒu tốn t i nguyŒn mÁy: tốn CPU v bộ nhớ v mỗi
lần gọi đệ quy, chương trình lại yŒu cầu cấp phÁt thŒm kh ng
gian nhớ để lưu trữ kết quả v thực hiện chương trình.
- Vấn đề n o giải quyết đươc bằng đệ quy đều c thể giải quyết
được bằng v ng lặp. Chọn đệ quy vì đệ quy thể hiện cÁch giải
quyết vấn đề rı r ng, tự nhiŒn v dễ hiểu, dễ sửa lỗi.
Thank you for reading this tutorial!
Document Outline

• Đệ quy