Có thể giải hầu như mọi bài toán bằng phương pháp đệ quy?

mình hỏi câu này có vẻ hơi kì cục, nhưng sau khi mình học prolog xong mình thấy nó hoàn toàn là lập trình khai báo và đệ quy, mà hầu như bài toán hay yêu cầu nào cũng phân tích về hướng đệ quy đc, mình chưa nói đến phần hiệu suất, tốn bộ nhớ hay gì, chỉ cần giải đc bài toán là đc, thì cái suy nghĩ trên của mình có đúng ko nhỉ??

2 Likes

vòng lặp có thể chuyển thành đệ quy được, do đó bài toán nào có xuất hiện vòng lặp thì có thể đổi sang dạng đệ quy, tất nhiên không phải lúc nào code đệ quy cũng sẽ clean và ngắn hơn dùng vòng lặp

3 Likes

một bài toán giải được bằng đệ quy khi nó có thể tách ra thành các bài toán nhỏ hơn. tức nếu có một bài toán không thể tách nhỏ thì nó sẽ không thể đệ quy. trong thực tế, thì hầu hết các bài toán lớn đều dựa trên các bài toán nhỏ, nên ta thấy hầu hết các bài toán đều giải được bằng đệ quy (nếu có vô hạn bộ nhớ)

có một bài toán không thể đệ quy đó là phép cộng 2 số a + b. vì phép cộng đơn giản không thể tách ra bài toán nhỏ hơn được.

1 Like

Phép cộng có thể cài đặt đệ quy được nhé. Bạn có thể tìm hiểu Church Number.

https://www.cs.unc.edu/~stotts/723/Lambda/church.html

4 Likes

Không biết có cách nào tối ưu hơn không nhưng để xóa folder mà bên trong có chứa nhiều file và folder lồng nhau thì phải dùng đệ quy.

1 Like

graph/tree -> bfs, dfs

1 Like

tìm hiểu giải thuật khử đệ quy bạn nhé, tùy bài toán sẽ có cách khử khác nhau

1 Like

Vòng lặp for xử đẹp luôn.
Cách tối ưu chắc dùng lib / framework.
Ví dụ:

QDir(path).removeRecusion();

=)))

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?