Download miễn phí Pascal - Thuật toán đệ quy
Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đối tượng chỉ
bằng một số hữu hạn các mệnh đề. Tuy nhiên, đặc tính này của đệ quy lại vi
phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong thuật toán
phải được xác định ngay tại thời điểm bước đó được thi hành, nhưng với
thuật toán đệ quy, bước thứ n không được xác định ngay trong ngữ cảnh của
nó mà phải xác định thông qua một bước thấp hơn.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
5. THUẬT TOÁN ĐỆ QUYThuật toán đệ quy là một trong những sự mở rộng cơ bản nhất của khái
niệm thuật toán. Như đã biết, một thuật toán cần thỏa mãn 3 tính chất :
– Tính hữu hạn.
– Tính xác định
– Tính đúng đắn
Tuy nhiên, có những bài toán mà việc xây dựng một thuật toán với đầy đủ
ba tính chất trên rất khó khăn. Trong khi đó, nếu ta xây dựng một thuật toán
vi phạm một vài tính chất trên thì cách giải lại trở nên đơn giản hơn nhiều và
có thể chấp nhận được. Một trong những trường hợp đó là thuật toán đệ quy.
Tư tưởng giải bài toán bằng thuật toán đệ quy là đưa bài toán hiện tại về
một bài toán cùng loại, cùng tính chất (hay nói một cách nôm na là đồng
dạng) nhưng ở cấp độ thấp hơn (chẳng hạn : độ lớn dữ liệu nhập nhỏ hơn,
giá trị cần tính toán nhỏ hơn, ....), và quá trình này tiếp tục cho đến lúc bài
toán được đưa về một cấp độ mà tại đó có thể giải được. Từ kết quả ở cấp độ
này, ta sẽ lần ngược để giải được bài toán ở cấp độ cao hơn cho đến lúc giải
được bài toán ở cấp độ ban đầu.
Trong toán học ta cũng thường gặp những định nghĩa về những đối tượng,
những khái niệm dựa trên chính những đối tượng, khái niệm đó.
Ðịnh nghĩa giai thừa
Giai thừa của một số tự nhiên n, ký hiệu n! được định nghĩa là :
0! = 1
n! = (n-1)!n với mọi n>0
Ðịnh nghĩa dãy số Fibonacci
f0 = 1
f1 = 1
fn = fn-1 + fn-2 với mọi n>1
Theo toán học, những khái niệm được định nghĩa như vậy gọi là định nghĩa
theo kiểu quy nạp. Chính vì vậy, đệ quy có sự liên hệ rất chặt chẽ với quy
nạp toán học.
Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đối tượng chỉ
bằng một số hữu hạn các mệnh đề. Tuy nhiên, đặc tính này của đệ quy lại vi
phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong thuật toán
phải được xác định ngay tại thời điểm bước đó được thi hành, nhưng với
thuật toán đệ quy, bước thứ n không được xác định ngay trong ngữ cảnh của
nó mà phải xác định thông qua một bước thấp hơn. Chẳng hạn, để tính được
giá trị phần tử thứ 5 của dãy Fibonacci theo định nghĩa ở trên, ta phải tính
f3+f4, nhưng ta chưa biết giá trị f3 và f4 tại thời điểm này. Ðến đây, ta phải lùi
lại để tính f3 và f4. Ðể tính f3 ta lại phải lùi về để tính f2,...Tất nhiên, là quá
trình tính lùi này phải dừng sau một số hữu hạn bước. Trong trường hợp này,
điểm dừng chính là giá trị f1 và f0.
Ưu thế của thuật toán đệ quy là ta chỉ cần giải bài toán tại một số trường hợp
đặc biệt nào đó, còn gọi là trường hợp dừng. Sau đó, các trường hợp khác
của bài toán sẽ được xác định thông qua trường hợp đặc biệt này. Ðối với
việc tính dãy Fibonacci, trường hợp dừng chính là giá trị của f0 và f1.
Nói một cách chính xác, mọi thuật toán đệ quy đều gồm hai phần:
Phần cơ sở Là các trường hợp không cần thực hiện lại thuật toán (hay
không có yêu cầu gọi đệ quy). Nếu thuật toán đệ quy không có phần này thì
sẽ dẫn đến bị lặp vô hạn và sinh lỗi khi thi hành. Vì lý do này mà người ta
đôi lúc còn gọi phần cơ sở là trường hợp dừng.
Phần đệ quy
Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại
thuật toán nhưng với một cấp độ dữ liệu thấp hơn.
...