递归数组有什么好处？

Question

Ruby支持递归数组（即包含自身的数组）:

a = []
# => [] 
a << a
# => [[...]] 
a.first == a
# => true 

这本质上很酷，但你可以用它做什么工作呢？

- hoffm

---

注意，这个例子很简单，因为 a.first 和 a 是完全相同的对象（具有相同的 object_id）。Ruby 同样支持独立递归结构的比较（例如 b = []; b << b; a == b # => true）。 - Marc-André Lafortune

Answer 1

一个没有区分边类型的有向图可以简单地将每个顶点表示为从该顶点可达的顶点数组。如果图中存在循环，那么你将拥有一个“递归数组”，特别是如果一条边可以指向同一顶点。

例如，这张图：

..可以用以下代码表示：

nodes = { a:[], b:[], c:[], d:[] }
nodes[:a] << nodes[:a]
nodes[:a] << nodes[:b]
nodes[:b] << nodes[:a]
nodes[:b] << nodes[:c]
p nodes
#=> {:a=>[[[...], []], [...]], :b=>[[[...], [...]], []], :c=>[], :d=>[]}

通常每个顶点的表示会更加“健壮”（例如，一个类实例，包含名称和出边数组属性），但是也可以想象一种情况，你需要非常轻量级的数据表示（对于非常大的图形），因此需要使用这样的最小表示。

- Phrogz

---

但这可能有什么应用呢？ - Simpleton

@Simpleton 有向图有哪些应用？很多！比如路径查找；建立基于单元格公式依赖的层次结构等。 - Phrogz

任何支持列表中引用元素的语言都可以做到完全相同的事情，不是吗？ - inger

@inger 当然可以。递归、自引用的数据结构当然不仅限于 Ruby。那只是 OP 所问的。 - Phrogz

Answer 2

Ruby支持递归数组。

对我来说问题是为什么它不应该支持呢？

一个数组只是一组引用。如果它检查每个元素并在其中之一引用了集合本身，则应抛出错误，因此防止递归或像Phrogz的示例那样使用它作为图形。

所以我不认为这是一个功能，但如果它是，我知道的大多数语言都有它，甚至Java…只需将Object用作数组元素即可。

- inger

---

除了 Ruby，我不知道还有哪种语言强烈支持递归数组。例如，在任何其他语言中，我认为您无法比较两个不同的递归数组。但在 Ruby 中可以这样做：a = []; a << a; b = []; b << b; a == b # => true - Marc-André Lafortune

@Marc-André，这是一个有趣的边角情况，不确定还有多少其他语言具有_那种程度_的支持。看着问题/示例，我（误？）解释了OP对“支持”的概念，因为它允许您_创建_递归数组 - 大多数语言都可以做到AFAIK。 - inger