Recursive definitions

A function may als be defined recursively.

fact :: Integer -> Integer
fact n = if n == 0 then 1 else n * (fact(n-1))

These are evaluated in the same way, through simplification of the given expression:

fact 0 
	-> if 0 == 0 then 1 else 0 * (fact(0-1)) 
	-> if True then 1 else 0 * (fact(0-1))
	-> 1

Note how the conditional is evaluated: evaluate the condition -> if true evaluate the left branch (then), otherwise evaluate the right branch (else). Given this, the only valid reduction sequence for $fact(0)$ is the one shown above, and this program terminates.

The expression $fact(-1)$ however, does not terminate. We could instead create a conditional function which covers these extraneous cases:

fact :: Integer -> Integer
fact n
	| n > 0		= n * (fact (n-1))
	| n == 0	= 1
	| n < 0		= error "negative argument"

Note that $error$ is a predefined function which causes immediate termination of the evaluator, with the given message.