Lecture 7-2
More Complex Recursion and Guards
Multiple Base Cases
Each base case represents a different stopping position:
isEven 0 = True
isEven 1 = False
isEven n = isEven (n - 2)
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)
Multiple Recursive Rules
More complex recursive functions may have more than one recursive rule.
evenSum 0 = 0
evenSum 1 = 0
evenSum x = if x `mod` 2 == 0
then x + evenSum (x - 1)
else evenSum (x - 1)
This function adds the even numbers less than the number provided. Hence it only adds x into the sum when it is even and if not it goes onto the next value.
It is important to make sure that the rules are comprehensive and that no value will crash the program.
Guards
This is the same function as before but using guards:
evenSum x
| (x == 0) = 0
| (x == 1) = 0
| (x `mod` 2 == 0) = x + evenSum (x - 1)
| otherwise = evenSum (x - 1)
To use guards, you write your function name and parameters. On the next line, with a pipe, you can write your test and return value:
func x
| x < 5 = "less than five"
| x > 6 = "bigger than five"
| x == 5 = "equal to five"
They are parsed from top to bottom and should take into account all cases as the interpreter won’t check for completeness. The word otherwise will cover all edge cases and make any partial function total.
Guards vs. Pattern Matching
- For tests of just equality the best way is to use pattern matching.
- Otherwise guards are to be used as it will save lines written.
Advice on Recursion
- When do you want to stop?
- These are the base cases.
- How do you make progress towards a base case?
- How do you make the problem smaller.
- There might be multiple cases to consider.
- These will be the recursive rules.
- What do you need to do to get to the smaller case?
- These will be the operations that you need to carry out within each rule.
Exercises
-
sign x | x < 0 = "negative" | x == 0 = "zero" | x > 0 = "positive" -
odd_product x | x == 1 = 1 | mod x 2 == 0 = odd_product (x - 1) | otherwise = x * odd_product (x - 1)