Đảo ngược chuỗi: Lần đệ quy vs lần lặp trong javascript

Question

một tháng trước tôi đã được một số thành viên của Google PTO phỏng vấn. Một trong những câu hỏi là: Đảo ngược một chuỗi đệ quy trong js và giải thích thời gian chạy bằng cách ký hiệu O lớn

này là giải pháp của tôi:

function invert(s){ 
    return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s; 
} 

Khá đơn giản, tôi nghĩ.

Và, về ký hiệu lớn-o, tôi nhanh chóng trả lời O (n) khi thời gian chạy phụ thuộc tuyến tính vào đầu vào. - Im lặng - và sau đó, anh ta hỏi tôi, sự khác biệt về thời gian chạy nếu bạn thực hiện nó bằng cách lặp lại là gì?

Tôi trả lời rằng đôi khi trình biên dịch "dịch" đệ quy thành lặp lại (một số ký ức ngôn ngữ lập trình) nên không có sự khác biệt về lặp lại và đệ quy trong trường hợp này. Btw vì tôi không có phản hồi về câu hỏi cụ thể này, và người phỏng vấn không trả lời "ok" hoặc "nope", tôi muốn biết liệu bạn có thể đồng ý với tôi hay không, nếu bạn có thể giải thích cho tôi biết 2 loại triển khai.

Cảm ơn rất nhiều và Kính trọng!

Answer 1

Giải pháp của bạn trông O (n ²) với tôi. Cuộc gọi đến substring rất có thể là O (n) - triển khai điển hình sẽ phân bổ không gian cho chuỗi mới và sau đó sao chép chuỗi con trên. [Nhưng xem bình luận.] Chuỗi nối + cũng có thể là O (n). Nó thậm chí có thể là trường hợp mà length là O (n) nhưng tôi nghĩ điều này là khá khó xảy ra.

---

Bạn đưa ra ý tưởng rằng trình biên dịch có thể chuyển đổi đệ quy thành lặp lại. Điều này đúng, nhưng nó hiếm khi được thực hiện bên ngoài các ngôn ngữ và sơ đồ chức năng; và thường là biến đổi duy nhất được áp dụng là loại bỏ đệ quy đuôi . Trong mã của bạn, đệ quy không nằm trong vị trí đuôi: sau cuộc gọi đệ quy tới invert bạn vẫn phải tính toán +. Vì vậy, loại bỏ đệ quy đuôi không áp dụng cho mã của bạn.

Điều đó có nghĩa là phiên bản lặp lại của invert sẽ phải được triển khai theo cách khác. Nó có thể có cùng độ phức tạp hoặc khác nhau, chúng ta không thể nói cho đến khi chúng ta nhìn thấy nó.

Answer 2

Một lưu ý phụ, để sử dụng đệ quy đuôi cho phép trình biên dịch thực hiện đệ quy của bạn dưới dạng vòng lặp, bạn không thể có trạng thái còn lại trên ngăn xếp. Để giải quyết vấn đề này, bạn có thể chuyển "trạng thái" này làm thông số bổ sung cho chức năng của mình:

function invert(sofar, s) 
{ 
    return (s.length > 0) ? invert(s.charAt(s.length-1)+sofar, s.substring(0,s.length-1)) : sofar; 
}