2

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)

Improve this question
3
  • 3
    expon x 0 = 1 is the base case. Read up on pattern matching. Once you get that the second question will be answered. Commented Mar 26, 2020 at 0:02
  • You might find the first answer in this Q&A helpful: How to write a recursion function in haskell. Commented Mar 26, 2020 at 0:09
  • The two-line definition is equivalent to expon x power = if power == 0 then 1 else x * (expon x (power - 1)). As written, the second equation isn't used if the first equation applies. Commented Mar 26, 2020 at 12:42

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Correction: unlike most languages, Haskell doesn't have a call stack. Stack overflows in Haskell are usually caused by having too many unevaluated "thunks" (this is a consequence of lazy evaluation). Certainly you will get a stack overflow from genuinely infinite recursion like this example, but it's not actually connected to a "call stack".
@RobinZigmond, is there a real operational difference between GHC's evaluation stack and a call stack, or is that more a matter of perspective?
@dfeuer I'm certainly no expert here, so I may not be correct on the finer details - but I would say there certainly is an "operational difference". You only have to see the difference between using foldl and foldl' on a huge list to see the difference - both use recursion, but only the former will overflow the stack. In practice, while this certainly isn't one of those cases, there are many real life questions about SO's in Haskell where the answer is to introduce more strictness, when thinking of it in terms of a call stack wouldn't help.
@RobinZigmond yes, fair point. I have chosen to explain it from a perspective of "call stack" model which is not actually answering correctly to the question "How do recursive functions work in Haskell". Answering the same question from a lazy model perspective (ie, explaining how thunks work and lazy evaluation) is a better approach to answer this question. I agree on that! Still, I will leave my "call stack" approach explanation as it might be useful for people coming from languages which use call stack model.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.