Recursive haskell and stack overflow

Question

As someone relatively new to Haskell and functional programming, and coming mainly from a Python background, I'd like to know why the following function results in a stack overflow in Haskell, even if I use a very low number like 4, or 5 as the input variable, whereas the exact same function in Python can process an integer of 20 and up without overflowing. Why is this so?

countStairs <0 = 0
countStairs 0 = 1
countStairs n = countStairs(n-1) + countStairs(n-2) + countStairs(n-3)

I've read other responses on Haskell and stack overflows that address code optimization and solving specific overflowing code, whereas I'm interested in understanding the specifc reason for the difference in how the two languages handle recursion here, or more generally why the Haskell code results in a stack overflow.

EDIT: I didn't include the full python code because this is my first question in Stack Overflow and I'm struggling to figure out how to get my Python to format properly (nice welcome from some of you, btw). Here it is, poor formatting and all, but the Python as written does work properly with the integer 20, whereas my undoubtedly poor Haskell has not. I've edited the Haskell code to show the corresponding code I originally omitted. I thought I was including the relevant recursive part, but obviously I was wrong to omit the base case. Still, as written, my Haskell stack overflows and my Python doesn't, and I'm still interested in learning why. Even though I don't come from a programming background, I really like learning Haskell and was just trying to learn some more. Thanks to those who tried to address the question in spite of my incomplete question.

def countStairs(n):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return countStairs(n-1) + countStairs(n-2) + countStairs(n-3)

myint = int(raw_input("Please enter an integer: "))
print countStairs(myint)

Python can run an infinite recursion without overflowing its stack, and in finite time?? — user445408
@Rahul: Well, it already has antigravity. Performing infinite computations can't be that much harder. — C. A. McCann
@EricS.Bullington Since it is a common "next mistake", please note that there is no automatic memoizing going on either. OTOH as the link shows, it isn't hard to add. — Thomas M. DuBuisson
-1 for not reporting what the exact same python program outputs for countStairs 20 — Ingo
Exact same program in python overflows. Huge stack trace is super helpful. ;) — Dan Burton

Adam Wagner Adam Wagner · Accepted Answer · 2011-12-31T05:06:59

Another way to add a terminating condition is to use a guard (this also addresses the <= 2 condition Corbin mentioned:

countStairs n | n > 0 = countStairs(n-1) + countStairs(n-2) + countStairs(n-3)
              | otherwise = 1

Update

Your updated Haskell example doesn't work because you misunderstand a how pattern matching works. You were expecting it to work like a guard (seeing as you tried to provide a boolean expression < 0 in a pattern match), however, that version of your function never matches (when you call the countStairs function). Consider this example:

countStairs < 0 = "Matched '< 0'"
countStairs   0 = "Matched '0'"
countStairs   n = "Matched n"

main = do
    putStrLn $ countStairs (-1)  -- outputs: "Matched n"
    putStrLn $ countStairs 0     -- outputs: "Matched 0"
    putStrLn $ countStairs 20    -- outputs: "Matched n"

The interesting thing here is that your function actually compiles. To find out why, load the above code into ghci and type :browse. This will give you a list of the functions you've defined in this module. You should see something like this:

(Main.<) :: Num a => t -> a -> [Char]
countStairs :: Num a => a -> [Char]
main :: IO ()

You've got countStairs and main which both make sense. But you've also got this function called Main.<. What is this? You've redefined the < function in this module! In case you're not familiar, you can define infix functions (like +, <, >, etc.) like so:

infix <
a < b = True

-- also defined as
(<) a b = True

Normally, you need that infix FUNCTION_NAME to indicate your function is infix. But.. prelude already defines < as an infix function, therefore, you didn't need to, and instead just gave your own definition of <.

Now, lets rearrange our countStairs < 0 = "Matched '< 0'" like we did with a < b, and you get this:

(<) countStairs 0 = "Matched '< 0'"

In this function, countStairs is actually the first argument to your < function.

Here's one more example to drive home the point. Try running 1 < 0 in ghci (with your module still loaded). Here's what you'll get:

*Main> 1 < 0

<interactive>:1:3:
    Ambiguous occurrence `<'
    It could refer to either `Main.<', defined at foo.hs:3:13
                          or `Prelude.<', imported from Prelude

Normally, you'd get False, but in this case, ghci doesn't know if it should use your function (since < is just a regular function, not a special syntax) or the built-in (Prelude) version of <.

Long story short... use guards (or case, or if) for boolean tests, not pattern matches.

Recursive haskell and stack overflow

3 Answers