5

我通常在 ruby​​ 中迷上的一件事是递归模式。例如，假设我有一个数组，它可能包含数组作为无限深度的元素。因此，例如：

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

我想创建一个可以将数组展平为[1, 2, 3, 4, 5, 6, 7].

我知道这.flatten可以完成这项工作，但这个问题是我经常遇到的递归问题的一个例子——因此我正试图找到一个更可重用的解决方案。

简而言之 - 我猜这种事情有一个标准模式，但我想不出任何特别优雅的东西。任何想法表示赞赏

4

3 回答 3

5

递归是一种方法，它不依赖于语言。您在编写算法时要考虑两种情况：再次调用函数的情况（递归情况）和破坏它的情况（基本情况）。例如，在 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]

这有帮助吗？无论如何，这里显示的一个有用的模式是，当您在数组上使用 recusion 时，您通常需要flat_map（函数式替代each+ concat/ push）。

于 2012-05-21T07:43:53.293 回答
4

好吧，如果您对 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]
于 2012-05-21T07:43:51.463 回答
2

这是一个以尾递归样式编写的展平示例。 

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]

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

于 2013-12-11T07:34:21.887 回答