Lecture 7-1

COMP105 Lectures 2020-10-26

Recursion

There is no such thing as a while loop in Haskell so you must use recursion to complete the same task. This links into Assignment 1 as it leans heavily on recursion.

Factorial

A recursive function is one that calls itself:

factorial n = if n > 1
				then n * factorial (n - 1)
				else 1

A recursive function has:

• A base case.
  • The else case is the base case and is the state where recursion stops.
• One or more recursive rules that move us closer to the base case. When the base case is reached then the program will terminate.
  • The rule is calling ourself with n - 1
    • This makes progress to the base case as you are making n smaller and getting closer to 0.

Result of Factorial

factorial 4
> 4 * factorial 3
> 4 * 3 * factorial 2
> 4 * 3 * 2 * factorial 1
> 4 * 3 * 2 * 1
> 24

A good way to debug smaller iterations is to expand and follow the iterations to find the issue.

Factorial Using Pattern Matching

You can use pattern matching to remove the if in a recursive function:

factorial 1 = 1
factorial n = n * factorial (n - 1)

This is possible as Haskell processes functions from top to bottom. This means that first it will check if the argument matches 1 and if not fall through to the next case.

Another simple example:

f 1 = 1
f 3 = 2
f x = 0

If the pattern matching isn’t exhaustive then you may get an error if an unmapped input is supplied. An exhaustive function maps all inputs.

This style of pattern matching is similar to a case select.

Base Cases

Every function must have a base case:

• It gives a stopping condition for the recursion.
• It is usually the simplest case.
• You can have more than one base case.

Recursion with no base case will never terminate.

Comparison to Imperative Languages

while (condition)
{
	<lots of computation>
}

• Base cases are like the stopping condition.
• Recursive rules do the computation.
• Anything you can do in a loop can be done by recursion but there is no simple way to translate between the two.

Exercises

1. smallPrime 2 = True
   smallPrime 3 = True
   smallPrime 5 = True
   smallPrime 7 = True
   smallPrime x = Fase
   

2.  sumUpTo 1 = 1
    sumUpTo n = n + sumUpTo(n - 1)