Gian hàng bánRao vặtTư vấnHỗ trợThêm
  Bí quyết bán hàng Online  Thông báo  Đăng ký  Đăng nhập

Cho em hỏi về đệ quy trong ngôn ngữ lập trình C. cho em tài liệu phần này được không ạ?

nguyen xuan truong10/06/2009 - 18:25

Lượt xem 2.854
Cho em hỏi về đệ qui trong ngôn ngữ lập trình C. cho em tài liệu phần này được không ạ?
  • Cũ nhất
  • Mới nhất
  • Có ích nhất

BT

11/06/2009 - 09:47
Đệ 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 câu hỏi đệ quy có tính chất LIFO. Vì bạn là người mới học nên không cần quan tâm đến cách hàm đệ quy xử dụng bộ nhớ theo...
Đệ 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 câu hỏi đệ quy có tính chất LIFO. Vì bạn là người mới học 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 thì bạn này đừng ngại sử dụng đệ quy.
Đọc thêm

Phố mùa đông

11/06/2009 - 09:45
Bạn cứ hiểu đơn giản đệ quy là gọi lại chính nó
Eg:
void MyFunction(int n)
{
if (n = 0) {
return 0;
}
MyFunction(n-1);
// other statements
}
1. Bạn phải biết sơ qua về cấu trúc dữ liệu stack, cơ chế của nó mới hiểu được ! Vấn đề đệ quy, hàm và bộ nhớ được nói rất chi tiết trong các sách tiếng Anh, tiêu biểu như "C++ how to program" với các chủ đề như "function call stack", "stack frame", "activation records" ...
LIFO (Last In, First Out stack) --> "vào sau ra trước"

2. Đệ quy tốn bộ nhớ hơn và cũng rất tốn thời gian vì các hàm phải được khởi tạo "activation records" với các arguments, local variables, address return ... của nó
Bạn cứ hiểu đơn giản đệ quy là gọi lại chính nó
Eg:
void MyFunction(int n)
{
if (n = 0) {
return 0;
}
MyFunction(n-1);
// other statements
}
1. Bạn phải biết sơ qua về cấu trúc dữ liệu stack, cơ chế của nó mới hiểu được ! Vấn đề đệ quy, hàm và bộ nhớ được nói rất chi tiết trong các sách tiếng Anh, tiêu biểu như "C++ how to program" với các chủ đề như "function call stack", "stack frame", "activation records" ...
LIFO (Last In, First Out stack) --> "vào sau ra trước"

2. Đệ quy tốn bộ nhớ hơn và cũng rất tốn thời gian vì các hàm phải được khởi tạo "activation records" với các arguments, local variables, address return ... của nó

Vui lòng đăng nhập ID VATGIA để gửi trả lời của bạn