Bài Toán Đệ Quy | Sk4eo

Trong thân của một hàm, nếu nó gọi tới chính hàm đó để xử lý bài toán thì gọi là hàm đệ quy (Tự mình bắt mình làm ấy mà). Có điểm giống với quy nạp toán học.

1. Đặc điểm – Mỗi một lần hàm tự gọi đệ quy đến nó thì máy tính sẽ tự tạo ra một biến cục bộ mới. – Có bao nhiêu lần hàm gọi đệ quy thì sẽ có bấy nhiêu lần thoát ra khỏi hàm.(Kiểu như lặp hàm). – Khi thoát ra ngoài hàm đệ quy thì một loạt các biến cục bộ tạo ra do dùng đệ quy lúc này mới được giải phóng, và chúng sẽ giải phóng trước các biến cục bộ(sinh ra do đệ quy) tạo ra sau.

– Sử dụng đệ quy là một phương pháp làm cho chương trình ngắn gọn, dễ hiểu nhưng nó sẽ làm tốn bộ nhớ và thời gian nếu như cấu trúc hàm đệ quy ‘phức tạp’.

2. Sử dụng đệ quy:

– Chỉ sử dụng hàm đệ quy khi có suy biến. – Trong một trường hợp tổng quát bài toán có thể đưa về cùng dạng. Nhưng giá trị thay đổi, sau một loạt thay đổi nó phải đưa về trường hợp suy biến.

Ví dụ:

C Code: Lựa chọn code | Ẩn/Hiện code unsigned long fac(int n) // Hàm tính giai thừa { if(n==0) return (1); // Trường hợp suy biến. return (n*fac(n-1)); // Gọi đệ quy. }

Bây giờ bạn liên tưởng hàm trên với hàm sau đây sẽ hiểu được phương pháp đệ quy.

3. So sánh Đệ quy – Vòng lặp Hình bên dưới đưa ra một số đặc điểm so sánh giữa Đệ quy và Vòng lặp để thấy ưu – nhược điểm của mỗi loại chương trình: 4. Phân loại đệ quy.

Xét theo cách lặp (cách thức tự gọi lại hàm) có thể chia đệ quy thành 4 dạng sau:

• Đệ quy tuyến tính
• Đệ quy nhị phân
• Đệ quy phi tuyến
• Đệ quy hỗ tương

4.1. Đệ quy tuyến tính: là dạng đệ quy thông thường như phần định nghĩa, trong thân hàm đệ quy sẽ được chia thành 2 phần: Điều kiện dừng và vòng lặp.

Ví dụ về đệ quy tuyến tính trong việc tính giai thừa 4.2.Đệ quy nhị phân: là dạng mở rộng của đệ quy tuyến tính. Nếu trong đệ quy tuyến tính chỉ gọi lại hàm 1 lần thì đệ quy nhị phân sẽ gọi lại 2 lần. Tùy theo yêu cầu bài toán có thể gọi lại nhiều lần hơn nữa, nhưng chung quy lại 1 dạng là đệ quy nhị phân Với dạng đệ quy này tôi sử dụng bài toán fibonaci để minh họa, ta thấy thấy rằng khi tính phần tử thứ n(n>=2) thì cần có giá trị của 2 phần tử trước nó. Như vậy cần gọi lại hàm fibonaci 2 lần để có được giá trị của 2 phần tử đó.

4.3.Đệ quy phi tuyến:Với 2 dạng đệ quy trên ta có thể dung được luồng chạy của đệ quy, và thấy rằng mỗi lần thực hiện hàm thì số lần gọi lại đệ quy không đổi. Còn đối với loại đệ quy phi tuyến thì trong mỗi hàm số lần gọi lại sẽ khác nhau. Để tạo sự khác biệt này ta có thể dùng hàm xét điều kiện trước khi gọi lại hàm hoặc có thể kết hợp vòng lặp.

Ví dụ cho dạng đệ quy phi tuyến là một bài toán dãy số. Ta thấy rằng khi tính giá trị F(n) khi n càng lớn thì số lần gọi lại hàm F( ) càng nhiều, ở đây chúng ta sử dụng vòng lặp để quy định số lần gọi lại hàm F( )

4.4 Đệ quy tương hỗ: Với dạng đệ quy tương hỗ, việc gọi hàm không đơn thuần là tự gọi nó mà còn có gọi đến hàm khác, và hàm kia có khả năng gọi lại hàm ban đầu. Cứ như vậy tạo vòng lặp xen kẽ nhau, và tất nhiên dù là lặp dạng nào thì cũng cần có điểm dừng. Ở đây cần tạo điểm dừng trên cả 2 hàm, nếu 1 trong 2 hàm không có điểm dừng thì đệ quy sẽ vô tận.

Ví dụ minh họa

20.997303 105.842854

Chia sẻ:

• X
• Facebook

Thích Đang tải...

Có liên quan