Ruby：标准递归模式

Question

在ruby中我常常陷入递归模式的困境，比如说，假设我有一个数组，它可能包含无限深度的数组作为元素。例如：

my_array = [1, [2, 3, [4, 5, [6, 7]]]]

我希望能创建一个方法，将数组摊平成[1, 2, 3, 4, 5, 6, 7]。

我知道可以使用.flatten完成此任务，但是这个问题是为了演示我经常遇到的递归问题 - 因此我正在尝试找到更可重用的解决方案。

简而言之 - 我猜测有一种标准模式用于此类事情，但我想不出特别优雅的解决方案。欢迎任何想法。

- PlankTon

Answer 1

递归是一种方法，它不依赖于语言。您编写算法时需要考虑两种情况：调用函数的递归情况和中止函数的基本情况。例如，在 Ruby 中执行递归压缩的方式：

class Array
  def deep_flatten
    flat_map do |item|
      if item.is_a?(Array)
        item.deep_flatten
      else
        [item]
      end
    end
  end
end 

[[[1]], [2, 3], [4, 5, [[6]], 7]].deep_flatten
#=> [1, 2, 3, 4, 5, 6, 7]

这个有用的示例是想帮到你吗？当你在数组上使用递归时，通常需要使用 flat_map（each + concat/push 的函数式替代方案）。

- tokland

---

感谢您的回复。我最初尝试使用类外的函数，这样就无法递归调用item.my_flatten...但是现在这个方法可行。谢谢！ - PlankTon

@PlankTon。将my_flatten编写为函数只需要对上面的代码进行一些小改动。但作为一种OOP语言，且my_flatten是一种通用算法，将其添加到数组中是有意义的。 - tokland

Answer 2

如果您了解一点C语言，只需访问文档并单击Ruby函数即可获取C源代码，所有内容都在那里。

http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-flatten

对于这种情况，这里提供了一个Ruby实现。

def flatten values, level=-1
  flat = []
  values.each do |value|
    if level != 0 && value.kind_of?(Array)
      flat.concat(flatten(value, level-1))
    else
      flat << value
    end
  end
  flat
end

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7] 

- peter

---

啊 - 连接。我一直在尝试递归调用函数本身，但这样做就可以了。干杯！ - PlankTon

Answer 3

这是一个尾递归风格编写的flatten示例。

class Array

  # Monkeypatching the flatten class
  def flatten(new_arr = [])
    self.each do |el|
      if el.is_a?(Array)
        el.flatten(new_arr)
      else
        new_arr << el
      end
    end

    new_arr
  end
end

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7]

红宝石

虽然看起来红宝石并不总是针对尾递归进行优化：红宝石是否执行尾调用优化？

- Aaron Sullivan