### 4 Tutorial 3: Recursion and Problem Solving

In this section we will continue the study of the two functions $f\left(x\right)$ and $g\left(x\right)$ from the previous tutorial.

Reading: Simon Thompson, Chapter 4 and 10.2

#### 4.1 Worked Example: Optimisation

A minimisation problem has the form

for some function $f\left(x\right)$. The problem is to find the smallest possible value for $f\left(x\right)$. Often, we also want to find the corresponding value of $x$.

One simple minimisation algorithm is obtained by imagining a ball rolling on the curve. It will always run down-hill, and eventually it will stop in a local minimum. We will implement this algorithm to find the $x$ value minimising the function $f\left(x\right)$ from the previous tutorial.

- 1.
- Open the module from the previous tutorial, with the definition of the
`f`

function. - 2.
- We need to decide how far the ball should roll per iteration. For the time being we make it a
constant, so add the following line to you module
`delta = 0.01`

- 3.
- Then we decide on the bounds for the search. We search for a minimum in the interval
$\left(-20,20\right)$,
and add the following lines to the module.
`low = −20`

high = 20 - 4.
- We shall implement the function
`fmin`

which takes a starting point ${x}_{0}$ as input, and returns a (local) minimum. First we add the type declaration to our module, with one input and one output:`fmin :: Double −> Double`

- 5.
- Now we can start adding definitions for fmin. Using guards, we can define one case at the time.
First of all, if the ball has reached the lower or upper bound, this bound value is returned:
`fmin x0 | x0 − delta < low = low`

This constitues a base case for recursion.

| x0 + delta > high = high - 6.
- If we find smaller function value to the left of x0, i.e. at x0-delta, we move left and call the
function recursively with the new starting point. Similarly, we move right if this gives a smaller
function value.
`fmin x0 | f (x0 − delta) < f x0 = fmin (x0 − delta)`

| f (x0 + delta) < f x0 = fmin (x0 + delta) - 7.
- If neither moving left nor right reduces the function value, we must be in a local minimum which
is then returned:
`fmin x0 | otherwise = x0`

- 8.
- Save your module, start GHCi, and load (or reload) the module.
- 9.
- Test the
`fmin`

function, as follows`fmin 0`

- 10.
- Discuss: does it matter what value you give as starting point?

#### 4.2 Practice Problem: Bisection Method

In this tutorial we shall implement the Bisection Algorithm which is a simple numerical approach to equation solving. Consider the following equation as an example

Note that the right hand side is the function $g\left(x\right)$, so we can write $0=g\left(x\right)$ instead. Let’s not discuss whether a solution can be found analytically. We want to find some solution numerically.

A couple of observations are easy to make.

- 1.
- $g\left(-10\right)<0$
- 2.
- $g\left(10\right)>0$
- 3.
- $g\left(x\right)$ is continuous

It follows from these three observations that $g\left(x\right)$ has at least one root in the interval $-10<x<10$. Without considering the possibility of multiple roots, we want to find one such root.

You can look up the Bisection Method in most undergraduate introductions to calculus. Let $g\left(x\right)$ be a continuous function and $\left(l,u\right)$ an interval so that $g\left(l\right)$ and $g\left(u\right)$ have different sign; then $g\left(x\right)$ has a zero in the interval $\left(l,u\right)$. The Bisection Method finds the midpoint $m$ in the interval $\left(l,u\right)$. If $g\left(l\right)$ and $g\left(m\right)$ have different sign, then there must be a zero in the interval $\left(l,m\right)$ and we use bisection recursively on this interval. Otherwise, we call it recursively on the interval $\left(m,u\right)$.

##### 4.2.1 Tasks

- 1.
- Open your editor and create a new Haskell module for this problem. Choose an appropriate name for the module.
- 2.
- Implement the function $g\left(x\right)$
described above in Haskell. The type description should be
`f :: Double −> Double`

- 3.
- We are going to implement a
`bisect`

function, which can be used to find a zero of`f`

with a call like this:`bisect (−10) 10`

The arguments are resp. the lower and upper bound of the search interval and have type Double.- Write the type signature of
`bisect`

into your module file.

- Write the type signature of
- 4.
- The
`bisect`

function has to be a recursive function, so we need two cases. Use`l`

and`u`

to denote the bound of the search interval`(l,u)`

.- Base case
- If the difference
`l-u`

is very small, we can just take the average of`l`

and`u`

as the approximate solution. Write a guarded expression for the base case, e.g.`bisect l u | u−l < eps = ...`

choose an appropriate value for

`eps`

and add a defintion after the equal sign. - Recursive case
- If the search interval is larger, we split it in two, and find which half must
contain a root. Then we recursively continue the search in the relevant half. The
recursive call, with two different cases using guards, can look something like
this.
`bisect l u | fl*fm < 0 = bisect l m`

| otherwise = bisect m u

where ...You need to complete the

`where`

clause to define the midpoint`m`

and the function values`fm`

($g\left(m\right)$) and`fl`

($g\left(l\right)$).

- 5.
- Start ghci and load the module that you have written.
- 6.
- Test your bisection function by finding the root of
$g\left(x\right)$ in the
interval $\left(-10,10\right)$.
I.e. evaluate the following
`bisect (−10) 10`

Does the answer look reasonable when you compare to the plot of $g\left(x\right)$ in the previous tutorial?