Haskell Recursion
Recursion is when a function calls itself to solve a smaller version of the same problem. Every such function needs a stopping pattern that ends the calls.
fact stops at zero
The first equation stops the calls at 0. The second equation multiplies n by the fact of one less.
fact 0 = 1
fact n = n * fact (n - 1)
main :: IO ()
main = print (fact 4)sumTo adds down to zero
sumTo stops when its input reaches 0. Each other call adds its input to the sum of the smaller inputs.
sumTo 0 = 0
sumTo n = n + sumTo (n - 1)
main :: IO ()
main = print (sumTo 5)power stops at a count of zero
A wildcard stands for the base in the stopping equation because the base is not needed there. Each other call multiplies by the base once more.
power _ 0 = 1
power x n = x * power x (n - 1)
main :: IO ()
main = print (power 2 5)Example
countItems [] = 0
countItems (_:xs) = 1 + countItems xs
main :: IO ()
main = print (countItems [10, 20, 30])Key points
- Recursion: a recursive function calls itself with a smaller input.
- Stopping pattern: a stopping pattern gives a result without another call.
- Smaller input: each new call uses an input closer to the stopping pattern.
- Combining: each waiting call combines its piece with the result of the smaller call.
- Stopping first: the stopping equation is written before the self-calling equation.
In this example, countItems adds 1 for the first item of the list and calls itself on the rest, the empty pattern stops the calls at 0, and the ones add up to 3, which print writes.
Note
a definition with no stopping pattern would call itself forever.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Haskell Playground
Exercise
What does print (sumTo 3) print for a function where sumTo 0 is 0 and sumTo n is n plus sumTo (n - 1)?