Recursion refers to self-referential code. Most people are familiar with recursion in the form of *names* that are used before their values are fully computed. The classic Fibonacci function can be used to illustrate this. As you can see, the definition of `fib`

references itself.

```
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
```

The `fix`

function in Haskell calculates the *least* *fixed point* of the function provided as argument, if it exists. From numerical analysis, you may recall a fixed point as a value at which the output remains unaltered no matter how many times you apply the function to it. In other words, the following statement is true for all `f`

, for which the `fix`

function can be computed:

`f (fix f) = fix f`

To use the `fix`

function, we first need to a redefine `fib`

as a function that can be supplied to it. We define a new variable `f`

that represents the Fibonacci function, moving `fib`

over to the right side.

`let f = \fib -> \n -> if n < 2 then n else fib (n - 1) + fib (n - 2)`

In plain English, you could read this as: given the Fibonacci function and a number, we can calculate the value as (a) the number itself if it is less than 2, or (b) the sum of the Fibonacci function applied to the previous two numbers respectively.

Notice that the definition above no longer uses recursion; it simply accepts `fib`

and `n`

as arguments, and calculates the result.

We now find the *least fixed point* for the Fibonacci function, and apply it to the desired input. For instance, to find the 11^{th} Fibonacci number, we write:

```
import Data.Function (fix)
fix f 11
```

…and voila! it prints the result `89`

.

If you open up the source code of `fix`

, this is how it is defined:

```
fix :: (a -> a) -> a
fix f = let x = f x in x
```

Again, in plain English, replace `x`

with the supplied function `f`

applied to (`f`

applied to (`f`

applied to (…))), then return `x`

. You would *think* this would go into an infinite loop — and it does, if the function doesn’t converge — but it actually works! One of the advantages of a language with non-strict evaluation semantics like Haskell is the ability to work effectively with infinite regress.

That’s all for today, folks! 🖖