CODEWITHSUNDEEP
haskell
Eshiett
Eshiett

Reputation: 51

How do recursive functions work in Haskell

I saw this snippet of code online that recursively gets the exponent of a number.

expon :: Int -> Int -> Int
expon x 0 = 1
expon x power = x * (expon x (power-1))

The code works perfectly fine, but I have two questions:

  1. What is the importance of the line expon x 0 = 1

  2. since it is recursive why doesn't the power variable go below 0 (-1,-2) since power is always subtracted by 1, expon x (power-1)

Upvotes: 2

Views: 164

Answers (1)

akegalj
akegalj

Reputation: 379

Lets imagine that you didn't write your expon x 0 = 1 case and instead your function looks like:

expon :: Int -> Int -> Int
expon x power = x * (expon x (power-1))

running this in ghci will give us:

$ ghci
GHCi, version 8.8.3: https://www.haskell.org/ghc/  :? for help
Prelude> expon x power = x * (expon x (power-1))
Prelude> expon 2 3
*** Exception: stack overflow

When you see *** Exception: stack overflow error it usually means your program doesn't know how to stop (in haskell most likely triggered by infinite recursion).

Lets try to write down what happens to this function when we call it with expon 2 3 as shown above step by step:

expon 2 3 => 2 * (expon 2 (3 - 1))
2 * (expon 2 (3 - 1)) => 2 * (2 * (expon 2 ((3 - 1) - 1))
2 * (2 * (expon 2 ((3 - 1) - 1)) => 2 * (2 * (2 * (expon 2 (((3 - 1) - 1) - 1))))
...
...
something-very-very-very-very-long

and it never stops until it exceeds out of stack memory. Haskell is using stack https://en.wikipedia.org/wiki/Call_stack to track all the function calls that are not finished yet. If there are too many of unfinished functions on stack you might hit stack overflow https://en.wikipedia.org/wiki/Stack_overflow . If your machine would have infinite stack memory your program would never terminate. In this example expon 2 3 power variable was initially 3. In next recursive call it become 2, then 1, 0, -1, -2, ... , -10, -11, -12, ..., -101, ... So power variable in our case was actually negative at one point and at some point stack overflow happened (which is usually bad as your programs tend to crash).

To prevent it from happening you might want to define base case https://en.wikipedia.org/wiki/Recursion#base_case as you did with expon x 0 = 1:

expon :: Int -> Int -> Int
expon x 0 = 1
expon x power = x * (expon x (power-1))

with that in place our recursion would stop when power becomes equal to 0 (so it won't go bellow 0, -1, -2):

expon 2 3 => 2 * (expon 2 (3 - 1))
2 * (expon 2 2) => 2 * (2 * (expon 2 (2 - 1)))
2 * (2 * (expon 2 1)) => 2 * (2 * (2 * (expon 2 (1 - 1))))
2 * (2 * (2 * (expon 2 0))) => 2 * 2 * 2 * 1
2 * 2 * 2 * 1 => 8
program ends

EDIT: In fact, as Robin Zigmond explains in comments, Haskell is lazy language and "call stack" in Haskell is just a consequence of lazily evaluated expressions and unevaluated closures called thunks.

Upvotes: 2

Related Questions