Code
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
Example
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
Explanation
In my experience the only useful way to explain how a recursive method works is to show the result of salting the method with puts
statements and running an example. Moreover, to keep things straight when examining the output it's necessary to indent the output each a method calls itself and "undent" the output whenever the method returns. I've done that below for my method extract
. It requires time and patience to go through the calculations that are performed, but anyone doing so should gain a solid understanding of how this method works, and perhaps also learn something about recursive methods generally. There's no need, of course, to understand the code below that displays the calculations that are performed.
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}]