Đệ quy có quan trọng không?

Mình cũng đang trong tình trạng giống bạn vậy, thật sự không hiểu đệ quy là gì luôn:cry:

Các bạn đừng nản, ban đầu mình mới học cũng thấy đệ quy sao mà rối quá, nhưng chỉ cần 4-5 ngày nghiền ngẫm, suy nghĩ là ra thôi. Nếu hiểu được đệ quy tuyến tính thì mấy cái khác cũng trở nên đơn giản thôi bạn.
Nên nhớ, đệ quy là gọi lại chính nó, và đương nhiên nó phải có 1 đk dừng sau một số lần lặp lại nhất định.
Đệ quy là cần thiết nhé bạn, suy luận đơn giản bởi vì nó cần người ta mới tạo ra nó và đặt cho cái tên hay như vậy

Không thích dùng đệ quy vì ngốn tài nguyên và dễ tràn stack.

mỗi thuật toán đều có tầm quan trọng của nó, đôi qui đệ qui là cách tốt nhất để giải quết vẫn đề, đôi khi là cách duy nhất.

Hạn chế dùng đệ quy. Nó dẽ gây tràn stack và làm khó hiểu.
Nếu các thuật toán yêu cầu dùng đệ quy thì nên dùng.
Khi code dệ quy dù là loại nào thì cũng cần chú ý rõ ràng điều kiện suy biến và điiều kiện đệ quy.

đệ quy dễ hiểu hơn chứ? Bây giờ viết 1 cái binary tree, thử viết phương thức hủy cây nhị phân ko dùng đệ quy xem khó hay dễ?

đệ quy thì chỉ có 4 dòng:

void delNode(Node* p)
{
    if (!p) return;
    delNode(p->left);
    delNode(p->right);
    delete p;
}

ko xài đệ quy thì mấy dòng đây? Và viết thế nào?

Không có ý gây war, nhưng bạn có thể ví dụ cho mình đệ quy là các tốt nhất để giải quyết vấn đề và là cách duy nhất không ? Không tính mấy kiểu dạng : “Thầy bắt phải dung đệ quy”.

Thuật toán trên dễ dàng triển khai với một List và vòng lặp.
Vấn đề là thuật toán sẽ chạy như thế nào trên máy tính chứ không phải có bao nhiêu dòng, dễ hiểu hay không ?
Bây giờ bạn tạo cái binary tree có 100.000.000 node rồi dung đệ quy thử xem vấn đề

đúng rồi, đệ quy dễ hiểu nhưng nó chạy đôi khi ko tốt, vì nó xài memory trên stack, dẫn tới tràn stack. Nó dễ hiểu, dễ cài, nhưng ko phải là cách tốt nhất. Nói nó khó hiểu thì hơi bị lạ.

ko cần tree 100tr node đâu, 1-2tr node là đủ chết rồi, nếu chỉ là cây nhị phân bình thường, insert sao mà thành như cái linked list thì gây tràn stack thôi. Cách giải quyết nói cho hoa mỹ là chuyển memory xài từ stack lên heap, nói đơn giản là xài DFS. Nhưng người mới học ctdl cây nhị phân mà bắt hiểu sơ về lý thuyết đồ thị thì quá phức tạp.

nếu bạn để ý có thể thấy hầu hết các thuật xắp xếp, tìm kếm trong cấu trúc dữ liệu cơ bản như quick sort, merge sort, binary sort thì cách cài đặt bằng đệ qui là cawif đặt phổ biến nhất vì code rất ngắn và dễ hiểu, ngoài ra còn một số bài toán nổi tiếng như tháp hà nội , Ackermann function. còn vụ đệ qui là cách duy nhất thì có vẻ mình đã sai về cơ bản để qui là stacks nên bài nào giari được bằng đệ qui chắc chắn sẽ giair được bằng lặp và rẽ nhánh.

Cảm ơn mọi người đã cho ý kiến.

Cá nhân mình thấy chỉ có duy nhất đệ quy làm mình phải nháp ra giấy =]] (tính tới thời điểm này)

Nhiều khi muốn chuyển đệ quy hỗ tương sang đệ quy nhị phân phải dùng kiến thức toán học (như chuyển vế, giải phương trình, …) nữa :))

Chắc đệ quy sẽ là 1 cuộc hành trình dài đây, trong slide thầy Phương, nó còn nói mấy thuật toán + bài toán “trên trời dưới đất” nữa

Ví dụ của bạn đúng, nhưng đó là những ví dụ nhỏ khi mà số lượng các phần tử là tương đối nhỏ. Nhưng nếu số phần tử tăng lên nó mới gây vấn đề.

Chỉ dùng đệ quy chỉ khi không còn cách nào khác để giải quyết 1 bài toán, đệ quy chẵng qua nhằm giúp code ngắn gọn, dễ nhìn chứ độ phức tạp vẫn như các cách thông thường thôi.

Đệ quy thường là giải pháp đầu tiên và nhanh nhất mà ta nghĩ ra để giải quyết vấn đề. Tại sao? Tại vì nó đơn giản. Phạm vi áp dụng: Các bài toán dạng chia để trị, quy hồi…
Chú ý: Đơn giản ý mình là bạn có thể chỉ dựa vào định nghĩa của số Fibinacci để viết một hàm đệ quy cực kỳ ngắn gọn như sau:

Fibo(int n)
{
    if(n == 0) return 0;
    if(n < 2) return 1;
    return  Fibo(n-1) + Fibo(n-2);
}

Cái ví dụ không nhanh đâu. Vì để tính Fibo(n) cần tính Fibo(n-1) và Fibo(n-2) trong khi tính Fibo(n-1) lại cần tính Fibo(n-2) và Fibo(n-3). Dễ thấy Fibo(n-2) cần tính 2 lần. @_@!

đầu tiên và nhanh nhất mà ta nghĩ ra

ý mình là “đầu tiên và nhanh nhất mà ta nghĩ ra”. Nghĩa là cách đơn giản nhất mà ta nghĩ đến ấy. Ta có thể nghĩ ra một giải pháp đơn giản cho bài toán chỉ bằng việc dựa vào định nghĩa và đệ quy.

Người ta nói là cách nhanh nhất nghĩ ra được chứ có nói chạy nhanh nhất đâu

Mình thường tìm các giải pháp khác trước khi nghĩ đến đệ quy. Vì nó làm tăng stack và gây khó khi dọc hiểu
vd

void Test(int a) {
    if(a) {
        cout << a << "\n";
        Test(a - 1);
    }
}

void Test(int a) {
    if(a) {
        Test(a - 1);
        cout << a << "\n";
    }
}

Cho ra hai kết quả khác nhau và dùng stack một cách không tường mình nên khó đê hiểu logic.

Vậy đệ quy có được áp dụng nhiều trong giải thuật và làm desktop app không mấy anh ?

Bản chất đệ quy là dùng stack thôi bạn, bất cứ bài toán nào đệ quy được thì đều có thể quy về stack (là bản chất của recursion) hoặc queue(là bản chất của iteration) để giải, nhưng dùng stack thì tránh bị stackoverflow + tiết kiệm bộ nhớ hơn hơn là dùng đệ quy. Nếu nắm rõ cách dùng stack + queue thì hiểu đệ quy ez như một trò đùa