title: Recursive Function in Haskell very slow
body: <p>I've written a simple Haskell program to solve a puzzle. The algorithm is correct and it produces the correct result for <code>n = 40</code>, which is 14466. However, for <code>n = 100</code> the program gets so slow that I haven't even been patient enough to wait it out.</p>
  
  <p>I don't understand why it's so slow, since I would expect it to cache all the results for the intermediate function calls, you know, with Haskell being a lazy language and all.</p>
  
  <p>My Compiler is GHCi 7.6.3.</p>
  
  <p>I've tried profiling, but this just tells me that 99.9% of the time is spent in the isLoosing function.</p>
  
  <pre><code>isLoosing :: Int -&gt; Int -&gt; Bool
  isLoosing x y
      | y &lt; x             = isLoosing y x
      | x == 0            = True
      | x == 1            = False
      | y `mod` x == 0    = False
      | otherwise         = and [ not (isLoosing (y-x*m) x) |
                                  m &lt;- [1..(y `div` x)] ]
  
  loosingSum :: Int -&gt; Int
  loosingSum n = sum  [ x + y |
                          x &lt;- [1..(n-1)],
                          y &lt;- [(x+1)..n],
                          isLoosing x y == True ]
  
  main = print $ loosingSum 40
  </code></pre>