Lặp lại nhanh hơn đệ quy hay ít dễ bị tràn bộ đệm?

Question

Tôi biết bạn có thể viết lại một hàm đệ quy bằng cách sử dụng một vòng lặp đơn giản bằng cách sử dụng một mảng như một hàng đợi đầu tiên trong hàng đầu của 'công việc còn lại để được thực hiện'. Tôi đã nghe điều này làm cho nó ít có khả năng có một tràn ngăn xếp.

Nhưng nếu ngăn xếp chồng không phải là một vấn đề (vì bạn không đệ quy rất sâu), có lý do nào để thích lặp lại quá mức không? Có nhanh hơn không?

Tôi chủ yếu quan tâm đến JavaScript trên V8.

Answer 1

Trong Javascript, không (không bắt buộc, và có lẽ không thể? Xem nhận xét) làm tối ưu đệ quy đuôi, đệ quy chậm hơn lặp lại (vì, trong hầu hết mọi ngôn ngữ, một hàm gọi là nhiều hơn đắt hơn nhảy) và có khả năng gây ra lỗi tràn ngăn xếp nếu bạn chấp nhận quá sâu (tuy nhiên, giới hạn có thể khá sâu; Chrome đã từ bỏ độ sâu đệ quy 16.316 trong thử nghiệm của tôi). Tuy nhiên, tác động hiệu suất đôi khi đáng giá khi bạn viết một hàm đệ quy và một số thứ khó thực hiện hơn mà không cần đệ quy (hàm đệ quy gần như luôn luôn là nhiều hơn ngắn hơn các đối tác lặp), ví dụ làm việc với cây (nhưng bạn không thực sự làm điều đó với Javascript nhiều anyway Chỉnh sửa: GGG đã đề cập rằng DOM là một cây và làm việc với điều đó rất phổ biến trong JS).

Answer 2

Việc đệ quy có thể thất bại nhanh hơn vì chức năng đệ quy vô hạn sẽ thổi ra ngăn xếp tạo ra ngoại lệ mà chương trình có thể phục hồi, trong khi một giải pháp lặp lại sẽ chạy cho đến khi bị dừng bởi tác nhân bên ngoài.

Đối với mã sẽ tạo ra kết quả đầu ra hợp lệ cho thời gian, chi phí chính của đệ quy là phí gọi hàm. Các giải pháp lặp đi lặp lại đơn giản là không có điều này, do đó, có xu hướng giành chiến thắng trong mã hiệu suất quan trọng bằng các ngôn ngữ không tối ưu hóa rõ ràng cho đệ quy.

Nó chắc chắn đáng chú ý trong điểm chuẩn, nhưng trừ khi bạn đang viết mã quan trọng hiệu suất, người dùng của bạn có thể sẽ không nhận thấy.

Điểm chuẩn tại http://jsperf.com/function-call-overhead-test cố gắng định lượng chi phí cuộc gọi chức năng trong các phiên dịch JS khác nhau. Tôi sẽ đặt cùng một điểm chuẩn tương tự như kiểm tra một cách rõ ràng đệ quy nếu bạn lo lắng.

---

Lưu ý rằng đuôi gọi đệ quy tối ưu hóa là khó khăn để làm một cách chính xác trong ECMAScript 3.

Ví dụ, một thực hiện đơn giản của mảng gấp trong JavaScript:

function fold(f, x, i, arr) { 
    if (i === arr.length) { return x; } 
    var nextX = f(x, arr[i]); 
    return fold(f, nextX, i+1, arr); 
} 

không thể mòn đuôi được tối ưu hóa vì cuộc gọi

fold(eval, 'var fold=alert', 0, [0]) 

sẽ eval('var fold=alert') bên trong cơ thể của fold, gây ra các cuộc gọi dường như đệ quy đuôi để fold để không thực sự đệ quy.

ECMAScript 5 thay đổi eval để không callable trừ thông qua tên eval, và chế độ nghiêm ngặt ngăn eval từ giới thiệu các biến địa phương, nhưng tối ưu hóa đuôi gọi phụ thuộc vào khả năng để xác định tĩnh nơi một cái đuôi gọi đi mà không phải lúc nào có thể bằng các ngôn ngữ động như JavaScript.

Answer 3

Điều này phụ thuộc ... Tôi đã hỏi cùng một câu hỏi khi tôi gặp lỗi "Tập lệnh chậm" trong IE8 trong hàm đệ quy. Và ngạc nhiên khi lặp lại thực sự chậm hơn.

Tôi đã đi bộ qua một cây tìm kiếm một nút cụ thể. Và tôi đã viết lại hàm đệ qui của tôi theo cách lặp lại (sử dụng ngăn xếp để giữ ngữ cảnh) bằng cách sử dụng phương pháp tương tự: https://stackoverflow.com/a/159777/1245231

Sau đó, tôi bắt đầu nhận được lỗi "Kịch bản chậm" hơn từ IE 8 so với trước đây. Làm một số hồ sơ xác nhận rằng phiên bản lặp lại thậm chí còn chậm hơn.

Lý do cho điều này có thể là sử dụng ngăn xếp cuộc gọi phương thức trong JS có thể nhanh hơn sử dụng mảng với các hoạt động push() và pop() tương ứng trong vòng lặp. Để xác minh điều này tôi đã tạo ra thử nghiệm mô phỏng cây đi bộ trong cả hai trường hợp: http://jsperf.com/recursion-vs-iteration-852 Kết quả là đáng ngạc nhiên. Trong khi trong Chrome phiên bản lặp lại là (trong trường hợp của tôi) 19% chậm hơn, trong IE8 phiên bản lặp lại chậm hơn 65% so với phiên bản đệ quy.