Download miễn phí Đề tài Đệ quy và cách khử đệ quy



Như chúng ta đã biết phương pháp đệ quy không phải bao giờ cũng là giải pháp hữu hiệu nhất. Cứ mỗi lần gọi đệ quy máy phải dành một số vùng nhớ để lưu trữ các trị, các thông số và biến cục bộ. Do đó, đệ quy tốn nhiều vùng nhớ, thời gian truyền đối mục, thiết lập vùng nhớ trung gian và trả về kết quả Vậy để khắc phục hạn chế đó người ta nói đến khử đệ quy. Khử đệ quy ở đây có nghĩa là biến một thủ tục đệ quy thành một thủ tục chỉ chứa vòng lặp mà không ảnh hưởng gì đến các yếu tố khác, chứ không phải là thay đổi thuật toán. Ví dụ như trong các hàm đệ quy tính n! và số Fibonaci F(n) ta có thể thay bằng một vòng lặp để tính. Trong trường hợp tổng quát, khử đệ quy là một việc làm khá phức tạp và khó khăn. Có thể bạn sẽ nói rằng, vậy thì cứ sử dụng đệ quy, vừa ngắn gọn, dễ hiểu, vừa dễ cài đặt. Nhưng có đôi khi, sự hạn hẹp của bộ nhớ dành cho chương trình con không cho phép chúng ta làm điều đó, hay chúng ta biết rằng, ngôn ngữ máy không có đệ quy, vì vậy các trình biên dịch đều phải có nhiệm vụ khử đệ quy. Và một lí do nữa là bạn có thể thực sự gặp rắc rối với thủ tục đệ quy của mình khi trong một môi trường lập trình mà không cung cấp khả năng gọi đệ quy


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-17-de_tai_de_quy_va_cach_khu_de_quy.mHAvp5S74A.swf /tai-lieu/de-tai-ung-dung-tren-liketly-54326/
Để 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:

giải thuật đệ quy có thể dẫn tới một tiến trình gọi đệ quy không kết thúc khi đó không có khả năng gặp trường hợp neo, vì vậy quan tâm đến điều kiện dừng của một giải thuật đệ quy luôn được đặt ra. Để kiểm soát quá trình gọi đệ quy của giải thuật đệ quy P người ta thường gắn thao tác gọi P với việc kiểm tra một điều kiện B xác định và biến đổi qua mỗi lần gọi P, quá trình gọi P sẽ dừng khi P không còn thỏa mãn.
Mô hình tổng quát của một giải thuật đệ quy với sự quan tâm đến điều kiện dừng sẽ là:
P if B then P [ S, P ] hay P P [ S, if B then P ]
Thông thường với giải thuật đệ quy P để đảm bảo P sẽ dừng sau n lần gọi ta chọn B là ( n > 0). Mô hình giải thuật đệ quy khi đó có dạng:
P ( n ) if ( n > 0 ) then P [ S , P ( n -1 ) ]; hay
P ( n ) P [ S , if ( n > 0) then P ( n – 1 ) ] ;
Trong các ứng dụng thực tế số lần gọi đệ quy ( độ sâu đệ quy ) không những phải hữu hạn mà còn phải đủ nhỏ, bởi vì mỗi lần gọi đệ quy sẽ cần một vùng nhớ mới trong khi vùng nhớ cũ vẫn phải duy trì.
1.2.2 Ví dụ:
Xét bài toán tìm một từ trong từ điển :
Ta có thuật toán dưới dạng giả mã như sau:
BEGIN
IF ( từ điển chỉ có một trang ) THEN ( tìm từ trong trang này )
ELSE
BEGIN
+ ( chia đôi từ điển );
+ ( xác định xem nửa nào của từ điển chứa từ cần tìm)
IF ( từ đó nằm ở nửa trước của từ điển )
THEN ( tìm từ đó trong nửa trước )
ELSE ( tìm từ đó trong nửa sau );
END;
END.
Ta thấy sau mỗi lần từ điển được tách đôi thì một nửa thích hợp sẽ lại được tìm kiếm bằng một cách như đã dùng trước đó. Có một trường hợp đặc biệt, khác với mọi trường hợp trước, sẽ đạt được sau nhiều lần tách đôi, đó là trường hợp từ điển chỉ còn duy nhất một trang. Lúc đó việc tách đôi ngừng lại và bài toán đã đủ nhỏ để ta có thể giải quyết trực tiếp bằng cách tìm từ mong muốn trên trang đó, chẳng hạn bằng cách tìm tuần tự. Trường hợp đặc biệt này gọi là trường hợp suy biến.
1.3 Ưu nhược điểm của đệ quy:
1.3.1 Ưu điểm:
Công cụ mạnh, diễn đạt tư duy rất rõ ràng, chặt chẽ.
Ngắn gọn, có khả năng định nghĩa một tập hợp rất lớn các đối tượng bằng một số các câu lệnh hữu hạn.
Làm chương trình trông đẹp mắt, dễ đọc, dễ hiểu và chương trình được nêu bật rõ ràng hơn.
1.3.2 Nhược điểm:
Đệ quy tốn bộ nhớ nhiều hơn khi không đệ quy vì cứ mỗi lần gọi đệ quy lại cần thêm một vùng nhớ mới trong khi vùng nhớ cũ vẫn được duy trì.
Tốc độ thực hiện chương trình chậm hơn khi không đệ quy.
Chương II : CHƯƠNG TRÌNH CON ĐỆ QUY
2.1 Các phương pháp xây dựng chương trình con đệ quy:
2.1.1 Định nghĩa chương trình con đệ quy:
Định nghĩa:
Một chương trình con (hàm hay thủ tục) được gọi là đệ quy nếu trong quá trình thực hiện nó có phần phải gọi đến chính nó.
2.1.2 Cấu trúc của một chương trình con đệ quy:
Cấu trúc chính của một chương trình con đệ quy gồm hai phần: Phần cơ sở và phần đệ quy.
Phần cơ sở: Chứa tác động của hàm hay thủ tục với một số giá trị cụ thển ban đầu của tham số.Nó bao gồm các trường hợp dừng mà có thể được giải quyết ngay (trường hợp duy biến).
Phần đệ quy: Định nghĩa giá trị cần tác động cho giá trị hiện thời các tham số bằng các tác động đã được định nghĩa trước đây với các kích thước tham số nhỏ hơn (Là phần trong thuật toán có yêu cầu gọi đệ quy,tức là yêu yêu cầu thực hiện lại thuật toán ở cấp độ nhỏ hơn (điều kiện kiểm soát đệ quy)).
- Ví dụ : Hàm tính giai thừa của số tự nhiên n ( tính n! ).
Ta có chương trình con đệ quy sau:
Function gt ( n: byte ) : longint;
Begin
If n= 0 then gt:= 1 ( phần cơ sở )
Else gt:= n* gt ( n - 1); ( phần đệ quy )
End;
Trong ví dụ trên, qui trình thực hiện như sau:
Khi có lệnh gọi hàm, chẳng hạn:
x := gt(3);
thì máy sẽ ghi nhớ là:
gt(3) := 3 * gt(2); và đi tính gt(2)
kế tiếp máy lại ghi nhớ:
gt(2) := 2 * gt(1); và đi tính gt(1)
Theo định nghĩa của hàm thì:
gt(1) := 1;
Máy sẽ quay ngược lại:
gt(2) := 2 * 1; cho kết quả là 2
Tiếp tục:
gt(3) := 3 * 2; cho kết quả là 6
Như vậy kết quả cuối cùng trả về là 6. Ta có: 3! = 6.
Một ví dụ khác như sau: Ta xây dựng chương trình con tính số fibonaci.
Function Fibo ( n: integer) : integer ;
Begin
If ( n = 1) or ( n = 2 ) then Fibo := 1
( phần cơ sở)
Else Fibo := Fibo ( n - 1) + Fibo ( n - 2) ;
( phần đệ quy);
End;
2.2 Phương pháp xây dựng chương trình con đệ quy:
Để xây dựng giải thuật một bài toán có tính đệ quy bằng phương pháp đệ quy ta cần thực hiện tuần tự 3 nội dung sau:
Thông số hóa bài toán.
Tìm các trường hợp neo cùng giải thuật giải tương ứng.
Tìm giải thuật giải trong trường hợp tổng quát bằng phân rã bài toán theo kiểu đệ quy.
Thông số hoá bài toán.
Tổng quát hóa bài toán cụ thể cần giải thành bài toán tổng quat (một họ các bài toán chúa bài toán cần giải), tìm ra các thông số cho bài toán tổng quat đặc biệt là nhóm các thông số biểu thị kích thước của bài toán-các thông số điểu khiển (các thông số mà độ lớn của chúng đặc trưng cho độ phức tạp của bài toán, và giảm đi qua mỗi lần gọi đệ quy).
Ví dụ: n trong hàm FAC(n); a,b trong hàm USCLN(a,b).
Phát hiện các trường hợp suy biến (neo) và tìm giải thuật cho các trường hợp này.
Đây là các trường hợp suy biến của bài toán tổng quat, là các trường hợp tương ứng với các giá trị biên cuả các biến điều khiển (trường hợp kích thước bài toán nhỏ nhất), mà giải thuật giải không đệ qui (thường rất đơn giản).
Ví dụ:
FAC(1)=1, USCLN(a,0)=a
Phân rã bài toán tổng quát theo cách đệ quy.
Tìm phương án (giải thuật) giải bài toán trong trường hợp tổng quat bằng cách phân chia nó thành các thành phần mà hay có giải thuật không đệ quy hay là bài toán trên nhưng có kích thước nhỏ hơn.
Ví dụ: FAC(n)=n*FAC(n-1).
Đệ quy là một công cụ cho phép người lập trình tập trung vào bước chính yếu của giải thuật mà không phải e sợ tại thới điểm khởi đầu về cách kết nối bước chính yếu này với các bước khác. Khi cần giải quyết một vấn đề, bước tiếp cận đầu tiên nên làm thường là xem xét một vài ví dụ đơn giản, và chỉ sau khi đã hiểu được chúng một cách kỹ lưỡng, chúng ta mới thử cố gắng xây dựng một phương pháp tổng quát hơn. Một vài điểm quan trọng trong việc thiết kế một giải thuật đệ quy được liệt kê sau đây:
Tìm bước chính yếu. Hãy bắt đầu bằng câu hỏi “Bài toán này có thể được chia nhỏ như thế nào?” hay “Bước chính yếu trong giai đọan giữa sẽ được thực hiện như thế nào?”. Nên đảm bảo rằng câu trả lời của bạn đơn giản nhưng có tính tổng quat. Không nên đi từ điểm khởi đầu hay điểm kết thúc của bài toán lớn, hay sa vào quá nhiểu trường hợp đặc biệt (do chúng chỉ phù hờp vói các bài toán nhỏ). Khi đã có được một bước nhỏ và đơn giản để hướng tới lời giải, hay tự hỏi rằng những khúc mắc còn lại của bài toán có thể được giải quyết bằng cách tương tự hay không, để sủa lại phương pháp của bạn cho tổng quát hơn, nếu cần thiết. Ngoại trừ những định nghĩa toán học thể hiện sự đệ ...

---