[Haskell-beginners] recursive and non recursive functions

[Brent Yorgey]

On Wed, Sep 18, 2013 at 12:41:54AM -0600, Dan Lior wrote:
> The following snippet is from a recent stack overflow post (by someone else). 
> 
> 
> 
> 7
> down vote
> accept
> I'd like to mention an important distinction:
> 
> cyclic' = [0,1] ++ cyclic'
> 
> cyclic'' = [0,1] ++ x
>     where x = cyclic''
> These two functions are recursive. But
> 
> cyclic = let x = 0 : y 
>              y = 1 : x
>          in x
> is not! It uses x internally, which is recursive, but the whole cyclic isn't. This is also why they're different when compiled into the core language.
> 
> This has some important practical implications, namely that recursive functions can't be inlined, but non-recursive can. 
> 
> Presumably, 
> 
> cyclic = let 
> 		x = [0,1] ++ y
> 		y = x
> 	       in x
> 
> is another "nonrecursive function".
> 
> I don't understand the distinction. I imagine that it is related to the let…in clause, but I don't think that I understand that either. Can someone try to clarify this ?
> 
> dan

The distinction is simply this: given a definition

  foo = ...

does foo show up in the ..., i.e. on the right-hand-side of its own
definition, or not?  If foo shows up in its own definition, it is
recursive.  If not, it is not recursive.  E.g. it is easy to see that in

  cyclic = let x = 0 : y 
               y = 1 : x
           in x

'cyclic' does not show up on the right-hand side of its own
definition.

-Brent