Two recursive called no finish (Towers of Hanoi)

1
votes

I programmed this function in haskell of the Towers of Hanoi problem. The function gives the numbers of steps from source stick to destination stick with only one alternative stick.

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

This function works fine ... until n, the number of discs, gets too high. GHCi does not finish. I know the complexity of this problem and I know it can't run faster.

For example, if I call it with n = 64, I can wait 20 minutes and get no output (it doesn't complete). Even if n = 20, it takes approximately 2 seconds.

With another implementation (below), the time is quite reduced.

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

Now, with n = 64, I get the result instantly. Obviously this has only one recursive call, but does that have such a large effect?

Could this be a problem of GHCi optimization?

2
haskellrecursiontowers-of-hanoi
There will be no optimization done in GHCi, and besides that, the GHC compiler does not optimize things like x + x to 2 * x. The reason that the latter is much faster than the former is because you are wrong about the complexity of your first solution (exponential) vs. your second (linear). – user2407038
@user2407038 I knew the exponential complexity, but I thought that GHCi transform x + x in 2 * x. Thanks a lot! – Pedro García
Common subexpression elimination – chepner
Auto-memoization (dynamic programming) would also help here, but the user would still need to ask for that explicitly. GHC does not optimize things in this way. – chi

2 Answers

6
votes

I suspect this actually is the function complexity. Your first version makes 2 recursive calls for every invocation, a complexity of O(2^n). For n=64, you're making 2^65 - 1 total calls. That's roughly 37 * 10^18 calls, so you're not going to see results in this lifetime with current computing power. At one call per microsecond, that's still well over 10 million years.

The second routine makes only one call per iteration; it's O(n).

To see the effect, try timing your first function at n = 19, 20, 21, 22. That should be enough to show the 2x time difference for each added disc.

2
votes

It would appear that the standard advice is to do common subexpression optimization yourself if you want to guarantee it is applied. See https://wiki.haskell.org/GHC/FAQ#Does_GHC_do_common_subexpression_elimination.3F. 

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