Recursion defines a function in terms of calls to itself on smaller or simpler input. In Haskell, it provides a way to traverse data or repeat work without mutable variables or conventional loops. A recursive definition needs patterns that describe when to stop and how to reduce the remaining work. section 2.4.1 section 3.1.2
Lists make the pattern clear. An empty list is the stopping case: its length is 0. A nonempty list has a first element and a remaining list, matched as x:xs. Its length is one plus the length of xs. Each call removes one element, so the input steadily approaches the empty-list case. section 2.4.1
listLength [] = 0 listLength (x : xs) = 1 + listLength xs
This definition pairs an empty-list base case with a recursive case that delegates the shorter tail to the same function. section 2.4.1
Use recursion on a list by following this shape:
- Match the empty list and return the result that needs no further work. section 2.4.1
- Match a nonempty list as x:xs, using x when needed and making the recursive call on xs. section 2.4.1
- Combine the current step with the recursive result, such as adding 1 after processing the tail. section 2.4.1
- Cover every input pattern; omitting a case makes the function partial and can produce a nonexhaustive-pattern error or undefined. section 2.4.1 section 2.4.2
Finding a character index
To find a character’s position, compare it with the first character. Return 0 when it matches; otherwise, add 1 and search the remaining characters. The empty-list case has no valid index, so an implementation using undefined fails when the character is absent. This demonstrates both recursive accumulation and the need to handle failure deliberately. section 2.4.1 section 2.4.2
Recursive calls can also simulate a loop in IO. Instead of changing a counter, define a function that accepts the current counter and produces an IO action. After reading and printing a line, call that function again with counter + 1. The parameter matters: Int -> IO () is a function that creates an action, not an IO action by itself. section 3.1.2 section 3.5
Pattern matching supplies the structural cases for recursive functions, while guards or conditionals can select behavior within a case. For indexing and rotation work, recursion supports list search; built-in indexing can then retrieve an element, with care required for invalid indices. section 2.6 section 2.4.2
