При написании рекурсивных алгоритмов, которые воздействуют на вложенные структуры данных с использованием рекурсивных функций, вы можете использовать throw
аналогично тому, как вы использовали бы break
или ранний return
при написании итерационных алгоритмов, которые воздействуют на плоские данные с использованием for
петли.
Например, предположим, что у вас есть список натуральных чисел, и вы хотите (по какой-то причине) написать функцию, которая будет возвращать true, если выполняется любое из следующих условий:
- Сумма всех элементов в списке больше 100
- Некоторый элемент в списке, если он равен 5
Скажем также, что вы всегда хотите выполнить эту проверку за один короткий проход по списку, вместо того, чтобы делать вызов reduce
для получения суммы и отдельный вызов any?
для поиска пятерок.
Вы, вероятно, написали бы некоторый код, похожий на этот (действительно, вы когда-нибудь написали код, подобный этому, на каком-то языке в какой-то момент вашей жизни):
def test(list)
sum = 0
for i in list
sum += i
if i == 5 || sum > 100
return true
end
end
return false
end
В большинстве языков не существует чистого эквивалента для взлома рекурсивного алгоритма, который использует рекурсивную функцию. В Ruby, правда, есть! Предположим, что вместо того, чтобы иметь список и хотеть проверить, содержат ли его элементы пять или сумму более 100, у вас есть дерево и вы хотите проверить, содержит ли его листьев пять или сумма более 100 при коротком замыкании и возврате, как только вы узнаете ответ.
Вы можете сделать это элегантно с помощью throw
/ catch
, например:
def _test_recurse(sum_so_far, node)
if node.is_a? InternalNode
for child_node in node.children
sum_so_far = _test_recurse(sum_so_far, child_node)
end
return sum_so_far
else # node.is_a? Leaf
sum_so_far += node.value
if node.value == 5
throw :passes_test
elsif sum_so_far > 100
throw :passes_test
else
return sum_so_far
end
end
end
def test(tree)
catch (:passes_test) do
_test_recurse(0, tree)
return false
end
return true
end
throw :passes_test
здесь действует немного как break
; это позволяет вам выпрыгнуть из всего стека вызовов ниже самого внешнего _test
вызова. В других языках вы могли бы сделать это либо путем использования исключений для этой цели, либо с помощью некоторого кода возврата, чтобы сообщить рекурсивной функции о прекращении рекурсии, но это более просто и просто.