Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Non tail-recursive function not blowing up in GHCi. Why?

I was expecting to see my stack blow with the following code.. yet it didn't:

*Main> let blowwss x = if x == 0 then 0 else (1 + blowwss (x-1))
*Main> blowwss 1000000
1000000

The function doesn't seem to be tail-recursive, so I'm wondering what may I be missing. Is GHCi's stack bigger than I thought (how can I see it's stack size, btw?). Is it using some kind of trampoline to get over this? Is it smart enough to convert the function to its iterative counterpart?

Thanks

like image 700
devoured elysium Avatar asked Dec 01 '13 14:12

devoured elysium


People also ask

Can a non-tail-recursive function be written as tail-recursive to optimize it?

Can a Non-tail Recursive Function Be Written as Tail-recursive to Optimize It? Any recursive algorithm can be rewritten as an iterative algorithm, and every iterative algorithm can be written as a tail-recursive algorithm.

What is non-tail recursion?

Non-Tail / Head Recursion A function is called the non-tail or head recursive if a function makes a recursive call itself, the recursive call will be the first statement in the function. It means there should be no statement or operation is called before the recursive calls.

What is recursion explain the difference between the tail and non-tail recursion with the help of stack?

The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. When one function is called, its address is stored inside the stack. So if it is tail recursion, then storing addresses into stack is not needed.

What is tail recursion in recursion and why it's important?

Definition: A special form of recursion where the last operation of a function is a recursive call. The recursion may be optimized away by executing the call in the current stack frame and returning its result rather than creating a new stack frame. See also collective recursion, iteration.


1 Answers

GHCi's stack is bigger than you think. IIRC, the default stack size is 500M for GHCi, whereas the default stack size for a compiled program is currently 8M. You can set a smaller limit yourself to see that you get a stack overflow (or you can increase your argument significantly).

$ ghci +RTS -K1M
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> let blowwss x = if x == 0 then 0 else (1 + blowwss (x-1))
Prelude> blowwss 1000000
*** Exception: stack overflow

Note that GHC has a stack size limit purely to prevent infinite / unexpectedly deep loops in situations that are most likely programming errors. In principle, the stack can grow indefinitely (constrained by the system memory, of course). Even if you specify a large stack size, the stack actually starts much smaller, but can grow up to the limit. There's currently discussion about possibly removing the limit completely in future versions of GHC.

like image 67
kosmikus Avatar answered Sep 21 '22 10:09

kosmikus