Код
def extract(h,target_key)
return [target_key, h[target_key]] if h.key?(target_key)
h.each do |kk,v|
next unless v.is_a?(Hash)
arr = extract(v,target_key)
return [kk,*arr] unless arr.nil?
end
nil
end
Пример
h = {
:a00=>{
:a10=>{
:a20=>{1=>2},
:a21=>{3=>4}
},
:a11=>{
:a22=>{
:a30=>{5=>6},
:a31=>{7=>8}
}
}
}
}
[:a00, :a10, :a20, :a21, :a11, :a22, :a30, :a31, 3, :a32].each do |k|
puts ":#{k} -> #{extract(h,k) || "nil"}"
end
target_key -> extract(h, target_key)
:a00 -> [:a00, {:a10=>{:a20=>{1=>2}, :a21=>{3=>4}},
:a11=>{:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}}]
:a10 -> [:a00, :a10, {:a20=>{1=>2}, :a21=>{3=>4}}]
:a20 -> [:a00, :a10, :a20, {1=>2}]
:a21 -> [:a00, :a10, :a21, {3=>4}]
:a11 -> [:a00, :a11, {:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}]
:a22 -> [:a00, :a11, :a22, {:a30=>{5=>6}, :a31=>{7=>8}}]
:a30 -> [:a00, :a11, :a22, :a30, {5=>6}]
:a31 -> [:a00, :a11, :a22, :a31, {7=>8}]
:3 -> [:a00, :a10, :a21, 3, 4]
:a32 -> nil
Объяснение
По моему опыту, единственный полезный способ объяснить, как работает рекурсивный метод, это покажите результат засоления метода с помощью операторов puts
и запуска примера. Более того, чтобы сохранить четкость при проверке выходных данных, необходимо делать отступы для выходных данных, которые каждый метод вызывает сам, и «отменять» выходные данные, когда метод возвращается. Я сделал это ниже для моего метода extract
. Требуется время и терпение, чтобы go выполнить выполненные вычисления, но любой, кто делает это, должен получить solid понимание того, как работает этот метод, и, возможно, также узнать кое-что о рекурсивных методах в целом. Разумеется, нет необходимости разбираться в приведенном ниже коде, отображающем выполняемые вычисления.
INDENT = 6
$col = 4-INDENT
def indent
$col += INDENT
end
def undent
$col -= INDENT
end
def prn
print " "*$col
end
def divide
puts "#<p></p>"
end
def extract(h,target_key)
divide
indent
prn; puts "entering extract"
prn; puts "h=#{h}"
prn; puts "h.key?(#{target_key}) = #{h.key?(target_key)}"
if h.key?(target_key)
prn; puts "returning #{[target_key, h[target_key]]}"
undent
divide
return [target_key, h[target_key]]
end
h.each do |kk,v|
prn; puts " kk=#{kk}"
prn; puts " v=#{v}"
prn; puts " v.is_a?(Hash) = #{v.is_a?(Hash)}"
prn; puts " skip key" unless v.is_a?(Hash)
next unless v.is_a?(Hash)
prn; puts " call extract(#{v},target_key)"
arr = extract(v,target_key)
prn; puts " arr=#{arr.nil? ? "nil" : arr} returned"
if arr
prn; puts " target key found"
prn; puts " returning [#{[kk,*arr]}]"
undent
divide
return [kk,*arr]
end
end
prn; puts "returning nil"
undent
divide
nil
end
extract(h,:a30)
entering extract
h={:a00=>{:a10=>{:a20=>{1=>2},..., :a31=>{7=>8}}}}}
h.key?(a30) = false
kk=a00
v={:a10=>{:a20=>{1=>2},..., :a31=>{7=>8}}}}
v.is_a?(Hash) = true
call extract({:a10=>{:a20..., :a31=>{7=>8}}}},target_key)
entering extract
h={:a10=>{:a20=>{1=>2},...,:a31=>{7=>8}}}}
h.key?(a30) = false
kk=a10
v={:a20=>{1=>2}, :a21=>{3=>4}}
v.is_a?(Hash) = true
call extract({:a20=>{1=>2}, :a21=>{3=>4}},target_key)
entering extract
h={:a20=>{1=>2}, :a21=>{3=>4}}
h.key?(a30) = false
kk=a20
v={1=>2}
v.is_a?(Hash) = true
call extract({1=>2},target_key)
entering extract
h={1=>2}
h.key?(a30) = false
kk=1
v=2
v.is_a?(Hash) = false
skip key
returning nil
arr=nil returned
kk=a21
v={3=>4}
v.is_a?(Hash) = true
call extract({3=>4},target_key)
entering extract
h={3=>4}
h.key?(a30) = false
kk=3
v=4
v.is_a?(Hash) = false
skip key
returning nil
arr=nil returned
returning nil
arr=nil returned
kk=a11
v={:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}
v.is_a?(Hash) = true
call extract({:a22=>{:a30..., :a31=>{7=>8}}},target_key)
entering extract
h={:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}
h.key?(a30) = false
kk=a22
v={:a30=>{5=>6}, :a31=>{7=>8}}
v.is_a?(Hash) = true
call extract({:a30=>{5=>6},
:a31=>{7=>8}},target_key)
entering extract
h={:a30=>{5=>6}, :a31=>{7=>8}}
h.key?(a30) = true
returning [:a30, {5=>6}]
arr=[:a30, {5=>6}] returned
target key found
returning [[:a22, :a30, {5=>6}]]
arr=[:a22, :a30, {5=>6}] returned
target key found
returning [[:a11, :a22, :a30, {5=>6}]]
arr=[:a11, :a22, :a30, {5=>6}] returned
target key found
returning [[:a00, :a11, :a22, :a30, {5=>6}]]
#=> [:a00, :a11, :a22, :a30, {5=>6}]