Đệ quy vs lặp lại liên quan đến việc sử dụng bộ nhớ

Question

Giả sử tôi có một đệ quy cũng như một giải pháp lặp lại (sử dụng ngăn xếp) cho một số vấn đề, ví dụ: đặt trước giao điểm của cây nhị phân. Với máy tính hiện tại, bộ nhớ khôn ngoan, có lợi thế nào khi sử dụng giải pháp đệ quy trên phiên bản lặp lại hoặc ngược lại cho rất lớn cây?

Tôi biết rằng đối với một số giải pháp đệ quy trong đó các vấn đề phụ lặp lại, có thêm thời gian và chi phí bộ nhớ nếu việc đệ quy được sử dụng. Giả sử rằng đây không phải là trường hợp ở đây. Ví dụ,

preOrder(Node n){ 
    if (n == null) return; 
    print(n); 
    preOrder(n.left); 
    preOrder(n.right); 
} 

vs

preOrder(Node n){ 
    stack s; 
    s.push(n); 
    while(!s.empty()){ 
     Node node = s.pop(); 
     print(node); 
     s.push(node.right); 
     s.push(node.left); 
    } 
} 

Answer 1

Nếu có một nguy cơ stack overflow (trong trường hợp này, bởi vì cây không đảm bảo được thậm chí bán cân bằng), sau đó là một chương trình mạnh mẽ sẽ tránh đệ quy và sử dụng ngăn xếp rõ ràng.

Ngăn xếp rõ ràng có thể sử dụng ít bộ nhớ hơn, vì khung ngăn xếp có xu hướng lớn hơn mức cần thiết để duy trì ngữ cảnh của các cuộc gọi đệ quy. (Ví dụ, khung ngăn xếp sẽ chứa ít nhất một địa chỉ trả về cũng như các biến cục bộ.)

Tuy nhiên, nếu độ sâu đệ quy bị giới hạn, thì không phải phân bổ động có thể tiết kiệm không gian và thời gian, cũng như thời gian lập trình viên. Ví dụ, đi bộ cây nhị phân cân bằng chỉ yêu cầu đệ quy đến độ sâu của cây, đó là nhật ký số lượng nút; đó không thể là một con số rất lớn.

Theo đề xuất của người bình luận, một trường hợp có thể là cây được biết là bị lệch sai. Trong trường hợp đó, bạn có thể recurse xuống các nhánh bên trái mà không lo lắng về tràn stack (miễn là bạn hoàn toàn chắc chắn rằng cây là đúng skewed). Kể từ khi cuộc gọi đệ quy thứ hai là ở vị trí đuôi, nó chỉ có thể được viết lại như một vòng lặp:

void preOrder(Node n) { 
    for (; n; n = n.right) { 
     print(n); 
     preOrder(n.left); 
     n = n.right; 
} 

Một kỹ thuật tương tự thường là (và nên luôn luôn có) áp dụng đối với quicksort: sau khi phân vùng, chức năng recurses trên phân vùng nhỏ hơn và sau đó lặp lại để xử lý phân vùng lớn hơn. Vì phân vùng nhỏ hơn phải nhỏ hơn một nửa kích thước của mảng ban đầu, điều đó sẽ đảm bảo độ sâu đệ quy nhỏ hơn log kích thước mảng ban đầu, chắc chắn ít hơn 50 khung ngăn xếp và có thể ít hơn rất nhiều .