Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Đệ qui trong ngôn ngữ C

  1. #1
    Ngày gia nhập
    02 2009
    Nơi ở
    Hà Nội_PTIT_cơ sở 1
    Bài viết
    15

    Angry Đệ qui trong ngôn ngữ C

    Mới học ngôn ngữ C mình không hiểu nghĩa của các từ:"đệ qui", "tính đệ qui của hàm", bạn nào biết giải thích hộ mình với!
    Đọc các vd mình chỉ thấy phương pháp sử dụng đệ qui nó na ná như phương pháp quy nạp của toán học (cùng giải quyết 1 vấn đề phức tạp thông qua 1 vấn đề khác đơn giản hơn) chứ chưa rút ra được khái niệm cụ thể!

    Nhân nói về "đệ qui", mình đọc sách thấy có mấy câu không hiểu:
    1."Việc làm đệ qui cần sử dụng bộ nhớ xếp chồng kiểu LIFO (Last In, First Out stack) để chứa các kết quả trung gian và do đó cần hết sức thận trọng lường trước việc kết thúc của quá trình đệ qui này."
    2."Nói chung ta nên tránh dùng đệ qui khi mà có thể dùng phép lặp để tính toán"
    -Câu 1 thì "mít đặc" hoàn toàn, đến cả nghĩa của từ viết tắt LIFO mà còn chịu...
    -Ở câu thứ 2, mình chỉ mang máng hiểu việc dùng đệ qui sẽ tốn nhiều ô nhớ hơn việc sử dùng phép lặp thôi chứ chưa biết cụ thể tại sao lại như thế?
    Mong các bạn giúp đỡ!
    PS: Cho mình hỏi luôn, các ô nhớ được sắp xếp bên trong RAM phải không các bạn?
    Cám ơn các bạn nhiều!
    Sorry, mình hỏi hơi "tham" trong topic này. Tại tất cả đều liên quan đến đệ qui, tách riêng ra thì hơi khó. Các bạn thông cảm nhá! ^^
    Đã được chỉnh sửa lần cuối bởi vuduykhanh : 02-03-2009 lúc 05:57 AM.

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    UIT
    Bài viết
    129

    Bạn cứ hiểu đơn giản đệ quy là gọi lại chính nó
    Eg:
    Code:
    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ó

  3. #3
    Ngày gia nhập
    10 2007
    Bài viết
    10

    Đệ 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 chỉnh sửa lần cuối bởi hvutrong : 02-03-2009 lúc 09:24 AM.

  4. #4
    Ngày gia nhập
    02 2009
    Nơi ở
    Da Nang
    Bài viết
    2

    Trích dẫn Nguyên bản được gửi bởi vuduykhanh Xem bài viết
    1."Việc làm đệ qui cần sử dụng bộ nhớ xếp chồng kiểu LIFO (Last In, First Out stack) để chứa các kết quả trung gian và do đó cần hết sức thận trọng lường trước việc kết thúc của quá trình đệ qui này."
    2."Nói chung ta nên tránh dùng đệ qui khi mà có thể dùng phép lặp để tính toán"
    -Câu 1 thì "mít đặc" hoàn toàn, đến cả nghĩa của từ viết tắt LIFO mà còn chịu...
    -Ở câu thứ 2, mình chỉ mang máng hiểu việc dùng đệ qui sẽ tốn nhiều ô nhớ hơn việc sử dùng phép lặp thôi chứ chưa biết cụ thể tại sao lại như thế?
    Mong các bạn giúp đỡ!
    PS: Cho mình hỏi luôn, các ô nhớ được sắp xếp bên trong RAM phải không các bạn?
    Cám ơn các bạn nhiều!
    Sorry, mình hỏi hơi "tham" trong topic này. Tại tất cả đều liên quan đến đệ qui, tách riêng ra thì hơi khó. Các bạn thông cảm nhá! ^^
    Câu 1: LIFO: Last In First Out Nghĩa là vào trước ra sau.
    Có thể cho bạn một ví dụ thế này cho dễ hiểu hi:
    bây giờ bạn có một cái thùng cứng hình vuông chẳng hạn, và bạn lần lượt bỏ vào cái thùng hình vuông đó những viên gạch được đánh dấu từ 1->10 chẳng hạn. Như vậy bây giờ bạn muốn lấy viên gạch thứ 9 ra thì bạn phải lấy viên gạch số 10 ra trước, tương tự bạn muốn lấy viên gạch số 5 ra, thì bạn phái lấy những viên gạch số 6 7 8 9 10 ra trước cái đã. Theo nguyên tắc đó được gọi là: LIFO. (kiểu ô sắp xếp ô nhớ dạng này gọi là STACK)

    Câu 2: Phải nói rằng rất khó để nói lúc nào thì nên dùng đệ qui lúc nào không nên. Vì nói cho cùng cái j cũng có 2 mặt. Vì khi chạy ct có hàm để quy, việc thực hiện nhiều lời gọi đệ quy như vậy sẽ tốn rất nhiều thời gian.
    Đối với hàm đệ quy thì tại mỗi thời điểm gọi lại chính nó, thì công việc thật sự chưa thực hiên xong, và các trạng thái của các biến... tại thời điểm đó sẽ được lưu lại, như vậy nếu trong hàm đệ quy có nhiều biến, hay thực hiện số lời gọi vô cùng lớn thì dẫn đến tràn bộ nhớ.

    PS: Cho mình hỏi luôn, các ô nhớ được sắp xếp bên trong RAM phải không các bạn?
    Đối với một người lập trình thì việc nắm chắc những khái niệm như: cấu trúc bộ nhớ, mô hình bộ nhớ .... là rất cần thiết và quan trọng. Đối với vấn đề này bạn nên tìm sách mà đọc để tham khảo (Mình thấy ở sách Ngôn ngữ lập trình C của Quách Tuấn Ngọc viết có nói rất rõ về vấn đề này, ở phần cấu trúc động và các mô hình bộ nhớ trong C ấy)
    #include <cuộc sống.h>
    #include <tình yêu.h>

  5. #5
    Ngày gia nhập
    02 2009
    Nơi ở
    Hà Nội_PTIT_cơ sở 1
    Bài viết
    15

    PS: Hồi nãy mình nói đệ quy na ná quy nạp phải ko? Xin lỗi, tớ nhầm, thực ra ý tớ là nó giống với công thức truy hồi hơn ^^. Hồi sáng ko hiểu nghĩ gì lại viết nhầm thành quy nạp! Các bạn thông cảm!

  6. #6
    Ngày gia nhập
    11 2007
    Nơi ở
    Hà Nội
    Bài viết
    520

    Mặc định Đệ qui trong ngôn ngữ C

    Trích dẫn Nguyên bản được gửi bởi vuduykhanh Xem bài viết
    Nhân nói về "đệ qui", mình đọc sách thấy có mấy câu không hiểu:
    1."Việc làm đệ qui cần sử dụng bộ nhớ xếp chồng kiểu LIFO (Last In, First Out stack) để chứa các kết quả trung gian và do đó cần hết sức thận trọng lường trước việc kết thúc của quá trình đệ qui này."
    2."Nói chung ta nên tránh dùng đệ qui khi mà có thể dùng phép lặp để tính toán"
    câu 1
    trong máy tính có 1 cấu trúc gọi là stack ,nó là 1 cấu trúc hoạt động theo ngyên tắc" vào trước ra sau"
    giả sử stack có độ lớn 0x100 bytes tức là tính offset ta đếm ra 0x100 ô và mỗi khi đẩy dữ liệu vào stack thì dữ liệu này sẽ được lấp đầy dần vào các ô này
    Thanh ghi SP sẽ chứa địa chỉ của ô nhớ trong stack vừa được push vào
    trong attachment :
    1: tình trạng stack trước khi có lệnh push phần tử có nội dung 0x00FE
    2: tình trạng stack sau khi có lệnh push phần tử có nội dung 0x00FE
    3: tình trạng stack trước khi có lệnh pop 2 lần

    mỗi khi gọi đệ quy , các tham số và địa chỉ trở về của hàm đều được push vào stack theo phương thức trên , sau đó máy gọi đến chính hàm đó để tính toán
    nếu chưa gặp phải điểm neo thì các tham số và địa chỉ trở về của hàm lại được push vào stack , cứ như vậy cho đến lúc gặp điểm neo
    khi gặp điểm neo , các giá trị (bao gồm giá trị neo và các tham số khác) được nạp vào hàm thông qua lệnh pop ra khỏi stack, tính toán , địa chỉ trở về của hàm được pop để lấy và quay về vị trí gọi
    bạn nên đọc thêm về stack
    có dịp mình sẽ viết tiếp về vấn đề này , bây giờ đi ngủ đã
    Attached Thumbnails Attached Thumbnails stack.jpg  

  7. #7
    Ngày gia nhập
    02 2009
    Nơi ở
    Hà Nội_PTIT_cơ sở 1
    Bài viết
    15

    Mình hiểu hơn một chút rồi, cám ơn mọi người nhiều!

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn