# Termination

Learn about the termination of programs.

## We'll cover the following

Once we start writing recursive functions, we need to worry about the **termination** of our programs (i.e. do they return a result in a finite amount of time?

## Non-termination

It is possible to write recursive functions that do not terminate.

```
loop :: Int -> Int
loop x = loop x
```

Here, the right hand side of the only equation of `loop`

is identical to its left hand side. So, the evaluation of an expression like `loop 1`

will make no progress:

```
loop 1
= loop 1
= loop 1
= ...
```

If we try to evaluate an expression like `loop 1`

in `ghci`

, it will loop forever. You can cancel computations in `ghci`

by hitting `CTRL + C`

on the keyboard.

This was, of course, a hypothetical example. But even when writing meaningful recursive functions, we need to be careful in making sure that they always terminate. To achieve this:

- At least one equation of the function must be a non-recursive base case.
- The recursive equations must modify the input argument such that the recursive calls get “closer” to a base case.

## Example: `compoundInterest`

Let’s check if our function `compoundInterest`

terminates on all inputs. Remember, the definition of the function was:

```
compoundInterest :: Int -> Double
compoundInterest 0 = 1000
compoundInterest n = 1.05 * compoundInterest (n - 1)
```

At first it might look like it does always terminate, since

- For the value
`0`

, the result is`1000`

, so we have a base case. - For other inputs greater than
`0`

, we go from`compoundInterest n`

into`compoundInterest (n - 1)`

in the recursive equation. So, the value of the function argument`n`

will get smaller and smaller in the recursive calls, until it finally reaches the base case`0`

and the recursion terminates.

However, there is one thing we overlooked here. The type of our function is

```
compoundInterest :: Int -> Double
```

So, we can call it on all integers, including negative numbers.

And trying to evaluate `compoundInterest (-1)`

in `ghci`

will lead to an infinite loop.

Our function `compoundInterest`

does not return results on all inputs. Thus, `compoundInterest`

is a **partial function**. It differs from the partial functions we have seen so far, though, as the equations of `compoundInterest`

can match any integer value.

In fact, when we try to evaluate `compoundInterest (-1)`

, the second equation will match (as the pattern variable `n`

matches any input value). The first few steps of the evaluation look like this:

```
compoundInterest (-1)
= 1.05 * compoundInterest (-1 -1)
= 1.05 * compoundInterest (-2)
= 1.05 * 1.05 * compoundInterest (-2 -1)
= 1.05 * 1.05 * compoundInterest (-3)
= 1.05 * 1.05 * 1.05 * compoundInterest (-3 -1)
= ...
```

and so on.

So, we have found a bug in the `compoundInterest`

function. How can we fix it? A pragmatic solution could be to simply treat negative inputs as we do the `0`

case:

Get hands-on with 1200+ tech skills courses.