Два рекурсивных называют без финиша (Ханойские башни)

Question

Я запрограммировал эту функцию в haskell проблемы Ханойских Башен. Функция дает количество шагов от исходного стика до конечного стика с помощью только одного альтернативного стика.

numStepsHanoi :: Integer -> Integer
numStepsHanoi 0 = 0
numStepsHanoi n = numStepsHanoi (n-1) + numStepsHanoi (n-1) + 1

Эта функция работает нормально... пока число дисков n не станет слишком большим. GHCi не заканчивается. Я знаю сложность этой проблемы и знаю, что она не может работать быстрее.

Например, если я позвоню с n = 64Я могу подождать 20 минут и не получить вывод (он не завершен). Даже если n = 20, это занимает около 2 секунд.

С другой реализацией (ниже) время значительно сокращается.

numStepsHanoi :: Integer -> Integer
numStepsHanoi 0 = 0
numStepsHanoi n = 2 * numStepsHanoi (n-1) - 1

Теперь с n = 64Я получаю результат мгновенно. Очевидно, что у этого есть только один рекурсивный вызов, но имеет ли это такой большой эффект?

Может ли это быть проблемой оптимизации GHCi?

Answer 1

Я подозреваю, что это на самом деле сложность функции. Ваша первая версия делает 2 рекурсивных вызова для каждого вызова, сложность O(2 ^ n). Для n=64 вы совершаете 2^65 - 1 общее количество звонков. Это примерно 37 * 10^18 вызовов, так что вы не увидите результатов в этой жизни при нынешней вычислительной мощности. Один звонок в микросекунду - это все еще более 10 миллионов лет.

Вторая подпрограмма делает только один вызов за итерацию; это O(N).

Чтобы увидеть эффект, попробуйте синхронизировать вашу первую функцию с n = 19, 20, 21, 22. Этого должно быть достаточно, чтобы показать двукратную разницу во времени для каждого добавленного диска.

Answer 2

Может показаться, что стандартным советом является самостоятельная оптимизация подвыражений, если вы хотите гарантировать ее применение. См. Https://wiki.haskell.org/GHC/FAQ#Does_GHC_do_common_subexpression_elmination.3F.

numStepsHanoi :: Integer -> Integer
numStepsHanoi 0 = 0
numStepsHanoi n = let steps = numStepsHanoi (n-1)
                  in steps + steps + 1