Termination

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: