Thường thì vòng lặp nhanh hơn, nhưng còn tuỳ trường hợp, tuỳ bài toán.
Khái niệm đệ quy? Đệ quy là gì?
1 Like
bác có vị dụ về trường hợp đó không. Với lại cho em hỏi tại sao vòng lặp nhanh hơn rồi mà còn dùng đệ quy làm gì cho phức tạp hóa vấn đề.
Đệ quy nó là 1 vòng lặp, nó sẽ lặp chính nó với 1 version đơn giản hơn vấn đề gốc… và khi lặp tới base case nó sẽ dừng và trả kết quả về
Vì đệ quy có ba loại, chia theo số lời gọi:
- Đệ quy tuyến tính. Cái này có thể thay bằng vòng lặp “dễ dàng” (nếu gọi đệ quy giữa hàm thì khó hơn xíu
) và bạn đang nhắc đến nó. - Đệ quy k-phân: Mỗi lời gọi sẽ phát sinh tối đa k (k >= 2) lời gọi đệ quy nữa, với k là hằng số. Như quick, merge, duyệt cây k-phân.
- Đệ quy phi tuyến: Mỗi lời gọi sẽ phát sinh n lời gọi đệ quy, với n thay đổi. Như in chỉnh, tổ hợp hay DFS.
Khử đệ quy (chuyển thành thuần lặp) k-phân và phi tuyến thì có khi bạc đầu luôn 
học đệ quy cho đầy đủ thì phải biết 3 loại này.
4 Likes
Đệ quy với lặp nhanh hơn hay chậm hơn thì tùy nhé.
Nếu 1 bài toán đã có sẵn thuật đệ quy thì có thể khử đệ quy, độ phức tạp thời gian như nhau.
Khử đệ quy đơn giản nhất là thay vì xài thread stack của hệ điều hành (function liên tục gọi chính nó), ta dùng stack riêng (implement bằng linked list chẳng hạn).
Phức tạp hơn thì tùy vấn đề, có khi khử xong thì chẳng cần stack nữa.
3 Likes
vậy làm sao để dừng cái vòng đệ quy đó hở bác. Nếu vậy thì ram to cỡ mấy cũng sẽ bị tràn.
Bạn lặp hay đệ quy thì cũng phải có điều kiện để dừng chứ.
Còn stack gì thì nếu chương trình của bạn cần tích lũy nhiều dữ liệu thì nó tràn là phải chịu, hoặc là nâng cấp máy, hoặc là xem lại thuật toán và cách tổ chức dữ liệu.
2 Likes
Vì vậy phải xác định điều kiện dừng và kiểm tra xem khi nào nó không dừng (tức là bug).
Mà đệ quy thì phải hiểu nó là cây (đồ thị), chứ không phải vòng lặp.
2 Likes
Không có gì là đặc biệt cả. Đệ quy là 1 phương thức được áp dụng rất nhiều trong các bài toán thực tế ( duyệt cây, sắp xếp, thuật toán tô màu, đồ hoạ …), chứ không viển vông như bạn nghĩ. Nếu bạn bỏ qua nó thì đó sẽ khiếm khuyết rất lớn trong việc học và thậm chí trong công việc. Không phải tự nhiên anh @ltd ảnh lại bỏ ra hẳn 1 bài để viết về nó đâu.
3 Likes
tks bạn, cách giải thích rất dễ hiểu
hiểu một cách dễ nhất: Đệ quy- thử sai quay lui. Cứ thử từng phương án. nếu sai thì quay lại thử phương án khác.Đúng thì đưa ra đáp án.
Về nguyên tắc thì thuật toán này giải quyết được mọi bài toán. Chỉ sợ máy tính ko đủ trâu bò với lại chạy hơi lâu
1 Like
Thật là rất quan trọng đấy nhé! nó giúp code chạy nhanh hơn nhưng còn phải tùy vào tường hợp mà sử dụng
Đệ quy nhiều khi chỉ là một cách viết lời giải thôi 
có khi còn chậm hơn vòng lặp.
3 Likes
đệ quy là gọi chính nó trong chính nó
Có code mới dễ hiểu bạn ạ
def tim_gai(trai_can_tim):
if trai_can_tim.XAU_TRAI:
break
if trai_can_tim.NGHEO:
break
ban_gai = tan_tinh_gai(trai_can_tim)
if ban_gai.CHUA_CO:
return tim_gai()
else:
# làm gì đó với "bạn" gái
2 Likes
Đệ quy trong Java là quá trình trong đó một phương thức gọi lại chính nó một cách liên tiếp. Một phương thức trong java gọi lại chính nó được gọi là phương thức đệ quy.
Một bài toán mang tính chất đệ quy khi nó có thể được phân rã thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn nữa. Cứ tiếp tục như thế cho đến khi không thể chia nhỏ được được hoặc đạt được kết quả mong muốn.
Chi tiết bạn xem ở đây.
struct Node* { int value; Node* pNext; }; chỉ cần thế này củng đủ để gọi là đệ quy rồi bạn, không cần phải là phương thức. Đệ quy chỉ là cái gì đó được gọi lại chính nó trong bản thân nó! Không nên thần thánh hoá về đệ quy, tuỳ ngữ cảnh mà xài cho phù hợp, giúp code viết gọn hơn và không cần phải dùng vòng lặp hay gì gì đó! Hiểu 1 cách đơn giản nếu 1 công việc đc lặp đi lặp lại nhiều lần trong một hàm thì nghĩ tới đệ quy và tất nhiên cần biết điều kiện để dừng cái hành động đó!
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?