Đây là bài viết về cách sử dụng phương pháp đệ qui trong lập trình do mình tìm hiểu. Mình chỉ chia sẽ nhưng cái mà mình biết để chúng ta cùng trao đổi;

Theo mình thì, đệ quy và quy nạp gần như là tương đương nhau, bạn có thể dùng quy nạp để chứng minh hàm đệ quy của bạn viết là đúng.

Đệ quy là khái niệm không khó và rất phổ biến, giải thích lại thì tốn thời gian mà chưa chắc đã đầy đủ hơn sách vở hoặc các nguồn có sẵn và rất nhiều trên mạng, vì vậy bạn chịu khó google, wikipedia, hay đọc sách là sẽ rõ ngay.

Mình chỉ tập trung vào tính chất LIFO của đệ qui. Vì tôi là người mới học lập trình nên không cần quan tâm đến cách hàm đệ quy xử dụng bộ nhớ theo kiểu stack như thế nào mà có thể hình dung theo một hướng trừu tượng hơn. Ví dụ bạn viết 1 hàm tính giai thừa cho n (n!) . Tạm gọi là gt (n);

gt(n)
{
if
n = 0 return 1
else
return g(n-1)*n
}

Hàm sẽ gọi giai thừa của n-1, rồi sau đó nhân với n để ra giai thừa của n.
Bây giờ giả sử bạn gọi :

gt(5)
gt(5) sẽ gọi gt(4)
gt(4) sẽ gọi gt(3)
gt(3) sẽ gọi gt(2)
gt(2) sẽ gọi gt(1)
gt(1) sẽ gọi gt(0)
gt(0) trả về giá trị 1

gt(1) sẽ trả về 1*gt(0) = 1
gt(2) sẽ lấy 2*gt(1) = 2*1 = 2
gt(3) sẽ lấy 3*gt(2) = 3*2 = 6
gt(4) sẽ lấy 4*gt(3) = 4*6 = 24
gt(5) sẽ lấy 5*gt(4) = 5*24 = 120

bạn tưởng tượng mỗi lần gọi hàm sẽ chiếm 1 phần của bộ nhớ máy tính, quy trình gọi sẽ là
gt(5)->gt(4)->gt(3)->gt(2)->gt(1)->gt(0)
sau khi gt(0) trả về 1, nó sẽ bị tống khứ khỏi bộ nhớ (vì đã hoàn thành nhiệm vụ và giữ lại chẳng để làm gì), bộ nhớ lúc này chỉ còn:
gt(5)->gt(4)->gt(3)->gt(2)->gt(1)
sau khi gt(1) trả về 1, nó cũng sẽ bị tống khứ khỏi bộ nhớ, bây giờ là:
gt(5)->gt(4)->gt(3)->gt(2)
….
cho đến gt(5) và rồi ko còn gì.

gt(0) được gọi sau cùng, nhưng được giải phóng đầu tiên, gt(1) được gọi kế cuối nhưng được giải phóng khỏi bộ nhớ ngay sau khi giải phóng gt(0).

gt(5) được gọi đầu tiên, nhưng được giải phóng khỏi bộ nhớ sau cùng.

Đó là lý do tại sao đệ quy mang tính chất LIFO.
Đệ quy chỉ nên tránh khi chúng ta có thể dùng phép lặp, nhưng không phải lúc nào tránh đệ quy cũng đem lại lợi ích về bộ nhớ vì đôi lúc, bất chấp dùng đệ quy hay vòng lặp thì bộ nhớ vẫn bị chiếm dụng 1 lượng như nhau. Nếu mới học như mình thì bạn đừng ngại sử dụng đệ quy nhé.

Còn đây là link down 1 số bái toán đệ qui để bạn có thể luyện tay thêm :d:http://www.mediafire.com/?hvk3k3e92h2ncfk

Chúc bạn học tốt

Advertisements