Phát hiện đệ quy vô hạn?

Question

Hãy giả sử tôi có một chức năng đang bò trên một mảng ...

flatten([a, b, c, d, [e, f, g, [h, i, j, k], l], m, n, o, p]) 
>> [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p] 

Flatten sẽ bò trên mã và cho mỗi mảng gặp đệ quy sẽ tham gia vào mảng đó và trả lại giá trị như vậy mà bạn có một căn hộ mảng.

này hoạt động cho đến khi chúng tôi có một mảng như:

a = []; 
a[0] = a; 

Điều này rõ ràng tạo ra đệ quy vô hạn:

Array[1] 
0: Array[1] 
0: Array[1] 
    0: Array[1] 
    0: Array[1] 
    0: Array[1] 
    0: Array[1] 
     ... 

Làm thế nào tôi có thể phát hiện hành vi này mà không modifiying các mảng như vậy mà các chức năng có thể đối phó Với cái này?

Answer 1

Bạn sẽ phải giữ một mảng truy cập của mảng trong hàm flatten() và kiểm tra sự tồn tại của chúng trong đó trước khi bạn nguyền rủa nó. Bạn sẽ phải chuyển danh sách các phần tử đã truy cập dưới dạng tham số thứ hai tới recurse.

function recurse(ar, visited) { 
    visited = visited || []; 

    function isVisited(obj) { 
     for (var i=0;i<visited.length;i++) { 
      if (visited[i] == obj) { 
       return true; 
      } 
     } 

     visted.push(obj); // but we've visited it now 
     return false; 
    } 

    // blah blah blah, do your thing... check isVisted[i] 
} 

này sẽ trở nên đắt để kiểm tra xem mảng của bạn là sâu, vì vậy bạn có thể lừa gạt và thiết lập một thuộc tính trên mỗi mảng bạn truy cập, và kiểm tra nó (nhưng sau đó tất nhiên, bạn đang sửa đổi mảng (nhưng không đáng kể)).

function recurse(ar) { 
    function isVisited(obj) { 
     var key = 'visited'; 
     var visited = obj.hasOwnProperty(key); 

     obj[key] = true; // but we've visited it now 

     return visited; 
    } 

    // blah blah blah, do your thing... check isVisted[i] 
} 

Answer 2

Nếu phát hiện đệ quy là một yêu cầu, bạn sẽ phải thương mại không gian bộ nhớ cho nó: tạo ra một mảng các đối tượng bạn phân tích cú pháp (các thông số bạn gửi đệ quy) và kiểm tra từng tham số mới chống lại nó. Nếu bạn đã phân tích cú pháp, hãy quay lại ngay lập tức.

Answer 3

Một cách thuận tiện để theo dõi các mảng đã truy cập sẽ là thêm thuộc tính "phẳng" vào mỗi mảng, có thể đặt nó thành một giá trị duy nhất cho mỗi thao tác. Không có điểm rối tung với một bản đồ riêng biệt khi mỗi mảng đã là một đối tượng hoàn toàn tốt.

Answer 4

Trong thế giới thực, bước 1 là tìm nhà phát triển vi phạm đã trao cho bạn một đối tượng tự tham chiếu và nhấn chúng bằng một cây gậy.

Vấn đề được giải quyết, tuy nhiên, bằng cách loại bỏ chúng dưới dạng tự tham chiếu tại chỗ. Biến chúng thành bản sao. Array.slice trả về các phần của mảng (bao gồm các bản sao hoàn chỉnh) mà không thay đổi bản gốc.

if(thisElement.constructor.prototype.slice){ //is it an array 
    thisElement = thisElement.slice(0); //now it's a new but identical array 
} 

Lưu ý rằng đây chỉ là chính tham chiếu mảng chính. Tham chiếu mảng nội bộ sẽ vẫn cần được thay đổi vì tham chiếu được sao chép vẫn trỏ vào cùng một thứ.

Ngoài ra, nếu bạn có thể đưa ra các giả định về các ký tự chắc chắn sẽ không có mặt, bạn có thể thấy slice/join rất hữu ích.

Answer 5

khác, cách bẩn hơn (nhưng tốt cho fuss tối thiểu) là chỉ cần sử dụng bộ mã hóa JSON:

var is_recursive = false; 

try { 
    JSON.stringify(my_recursive_object); 
} catch (e) { 
    if (e.name = 'TypeError') 
     is_recursive = true; 
    else 
     throw e; 
} 

tôi đã tìm thấy câu hỏi này tìm kiếm một câu trả lời tốt hơn, mặc dù - mặc dù điều này có thể giúp đỡ một người nào đó muốn một hack tốt đẹp ;-)