Structural recursion and base cases

The idea

Enter with list patterns and function equations understood. Structural recursion follows the shape of a value. A list function can handle [] directly and handle x:xs by combining x with the result for xs. The recursive call receives a shorter finite list, which supplies a clear termination argument. State the input assumption when a function depends on finiteness.

A base case contributes an identity or boundary result, such as zero for a sum or one for a product. Choose that value from the function’s meaning rather than copying another algorithm. To trace recursion, write the pending combinations until the empty case appears, then evaluate them back outward. Not every recursive function is efficient or stack-safe for every input; this chapter establishes correct structure before discussing performance refinements.

sumList :: [Integer] -> Integer
sumList [] = 0
sumList (x:xs) = x + sumList xs
main = print (sumList [2,5,1])

8

The expression expands to 2 + (5 + (1 + 0)). The empty list supplies the additive identity.