紅寶石：標準遞歸模式

我通常在ruby中關注的一件事是遞歸模式。例如，假設我有一個數組，並且可能包含數組作爲無限深度的元素。因此，例如：紅寶石：標準遞歸模式

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

我想創建可在陣列壓扁成[1, 2, 3, 4, 5, 6, 7]的方法。

我知道.flatten會完成這項工作，但這個問題的意思是我經常遇到的遞歸問題的一個例子 - 因此我試圖找到一個更可重用的解決方案。

總之 - 我猜這裏面有一個標準模式，但我不能拿出任何特別優雅的東西。任何想法表示讚賞

來源

2012-05-21 PlankTon

遞歸是一種方法，它不依賴於語言。您在編寫算法時考慮了兩種情況：再次調用函數的那些（遞歸情況）和打破它的情況（基本情況）。例如，要在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-21 07:43:53 tokland

感謝您的迴應。我最初嘗試使用類之外的函數，它不會遞歸地調用item.my_flatten ...但這是有效的。歡呼聲 – PlankTon

@PlankTon。把my_flatten寫成函數只需要對上面的代碼稍作修改。但是作爲一種OOP語言，並且'my_flatten'是一種通用算法，將它添加到Array中意義重大。 – tokland

好吧，如果你知道一點的C，你只需要訪問該文檔，然後單擊紅寶石函數來獲得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-21 07:43:51 peter

啊 - CONCAT。我試圖遞歸調用函數本身，但那會做。乾杯 – PlankTon

下面是一個用尾部遞歸樣式編寫的扁平化示例。

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

雖然它看起來像紅寶石並不總是尾遞歸優化：Does ruby perform tail call optimization?

來源

2013-12-11 07:34:21

紅寶石：標準遞歸模式

回答

相關問題