Khái niệm đệ quy? Đệ quy là gì?

#9

Thực ra hiểu đc concept với cách cài đặt là đc thôi mà, có gì mà chuyên sâu đâu :smile: sau này tuỳ lúc nếu gặp phải vấn đề mình thấy dạng đệ quy thì lôi ra dùng. mức độ quan trọng thì chắc cũng ko cao đâu :slight_smile:

#10

Em hiểu được cách concept với cài đặt. Tại hôm nay trùng hợp nghe thằng bạn nó cường hóa đệ quy nên kinh khủng :joy: Mà em thì học cứ bỏ qua nó :smiley:
Nên muốn hỏi vậy :smiley:

#11

bạn ấy cường hoá chính tỏ chắc mới học đệ quy, được khai sáng thấy hay quá nên làm màu tí ấy mà :stuck_out_tongue_closed_eyes:

#12

:joy: Em học qua lâu rồi. Đệ quy chỉ dùng cho một số bài đặc biệt và các thuật toán sắp xếp tìm kiếm.
:stuck_out_tongue: Nên bỏ nó lâu rồi. Giờ nghe thằng bạn nó chém thấy ghê ghê :stuck_out_tongue_closed_eyes:

#13

Xem ở link ở dưới. thật ra cái này cũng hay dùng đối với những cấu trúc dữ liệu dạng tree. viết vật cả ra ấy chứ.
https://onedrive.live.com/redir?resid=A8D2376A2C7ACABB!269&authkey=!APSBUTt6DfkJGN4&ithint=file%2Cpptx

#14

Quảng cáo ké:

4 Likes
#15

Nghe mn nói thấy đệ quy giống kiểu chia để trị nhỉ :slight_smile:

#16

Bạn nói ngược rồi nhé.

1 Like
#17

Đệ quy chắc có thể là từ hán việt, đệ là thằng em nhỏ hơn, quy là quay lại.
tính từ thằng bự nhất sau đó quay lại thằng đệ kế bên nó, chừng nào đụng thằng điều kiện dừng thì thôi, do vậy nên chắc kiu là đệ quy :smile:

#18

Quy là rùa ::))
(Cố viết cho đủ 20)

1 Like
#19

Đệ quy là cái này: 遞歸, tức là quay về theo thứ tự.
Minh họa trực quan nhất về đệ quy :smiley:

3 Likes
#20

cái đệ quy với vòng lặp thì cái nào nhanh hơn các bác

#21

Thường thì vòng lặp nhanh hơn, nhưng còn tuỳ trường hợp, tuỳ bài toán.

1 Like
#22

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 đề.

#23

Đệ 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ề

#24

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 :smiley: ) 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 :slight_smile: học đệ quy cho đầy đủ thì phải biết 3 loại này.

4 Likes
#25

Đệ 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
#26

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.

#27

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
#28

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
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?