javascript thực hiện chức năng đệ quy suy thoái

Question

Tôi đã làm những câu dưới đây trong một bài kiểm tra kỹ năng quá trình tuyển dụng:

var x = function(z) { 
    console.log(z);  
    if (z > 0) { 
     x(z-1); 
    } 
}; 

tại sao điều này là dần dần chậm như z có được cao hơn? đề xuất một phiên bản tốt hơn, giữ cho nó đệ quy.

Và tôi muốn biết câu trả lời chỉ để tìm hiểu về nó. Tôi trả lời rằng nó được chậm hơn vì như z tăng số lượng các cuộc gọi đệ quy tăng quá, nhưng tôi không thể cung cấp một phiên bản tốt hơn. Ngoài ra, tôi không biết nếu có bất kỳ lý do nào hơn nữa tại sao hàm trở nên chậm hơn khi z nhận được cao hơn.

Answer 1

Câu trả lời đúng sẽ là "Nó phải không phải chậm dần khi z trở lên". Trong thực tế, nó không có trong các bài kiểm tra đơn giản của tôi. Thử nghiệm của tôi tràn ngăn xếp trước khi có bất kỳ sự chậm lại nào.

Tôi không thể tưởng tượng bất kỳ cách nào khác để viết hàm trong khi duy trì tính chất đệ quy của nó.

Answer 2

Vì JavaScript không có cuộc gọi đuôi thực sự (chưa) những gì bạn đang gặp phải không phải là suy giảm dựa trên giá trị của z nhưng sự chậm lại dựa trên tăng trưởng ngăn xếp và khả năng thu dọn rác (GC) để dọn dẹp chồng các phạm vi cần thiết để giữ lại chức năng này.

Về lý thuyết, bạn có thể thay đổi hành vi này bằng cách sử dụng setImmediate và mẫu gọi lại để giải quyết vấn đề này. Việc sử dụng setImmediate cho phép phạm vi của vòng lặp thực hiện hiện tại không được sử dụng và được thu thập trong chu kỳ GC tiếp theo.

Vì vậy, một cái gì đó như:

var x = function x(z){ 
    console.log(z);  
    if (z > 0) { 
     setImmediate(function(){ 
      x(z-1); 
     }); 
    } 
}; 

Nhưng điều này sẽ không làm việc vì z được truyền xuống phạm vi cho setImmediate và do đó phạm vi trước đây của x không thể GC'd đúng cách.

Thay vào đó bạn phải sử dụng IIFE (Ngay Được triệu gọi hàm Expression) để đạt được những gì bạn đang tìm kiếm, kết hợp với việc sử dụng setImmediate để cho phép các chu kỳ thực hiện để có thời gian để cho phép GC:

var x = function x(z){ 
    console.log(z);  
    if (z > 0) { 
     setImmediate((function(newZ){ 
      return function(){ 
      x(newZ); 
      }; 
     })(z-1)); 
    } 
}; 

Trừ bất kỳ lỗi chính tả Tôi nghĩ rằng tôi đã đúng ở trên. Tất nhiên nếu bạn sử dụng ES6 bạn có thể viết tắt này rất nhiều là tốt.

Mặt khác của phương trình này là hiệu ứng spooling của console.log và bộ đệm thay đổi kích cỡ của bạn sẽ phải thực hiện điều này trong trình duyệt. Trong một thiết bị đầu cuối hệ điều hành các chi phí này sẽ được giảm thiểu như cuộn backbuffer bị giới hạn và bộ đệm phía sau được phân bổ trước và tái sử dụng.