Efficiently calculating the Fibonacci sequence using primitive recursion

Primitive recursive functions [1] are defined in terms of the initial functions. The initial functions are by definition primitive and include

• The nullary function \(n(x) = 0\)
• The successor function \(s(x) = x + 1\)
• Projection \(u^n_i(x_1, \dots, x_n) = x_i\)

Further primitive recursive functions can be created via composition \(f \circ g\) and via primitive recursion.

For some total function \(g\) and constant \(k\), \(h\) is said to have been obtained from \(g\) via primitive recursion if

$$ \begin{align} h(0) &= k\\ h(t + 1) &= g(t, h(t))\\ \end{align} $$

The smallest class of functions including the initial functions and is closed under primitive recursion defines the primitive recursive functions.

The Fibonacci sequence can be defined as follows

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

This isn’t defined in terms of primitive recursion. The following definition, for example, does not make use primitive recursion

$$ \begin{align} \mathtt{fib}(0) &= 0 \\ \mathtt{fib}(0) &= 1 \\ \mathtt{fib}(0) &= \mathtt{fib}(n - 1) + \mathtt{fib}(n - 2)\\ \end{align} $$

One thing to note is that this implementation is inefficient.

The fib function contains two recursive calls. If T(n) denotes the runtime of the fib function for a value, \(n\), then we now have

$$T(n) = T(n-1) + T(n-2)$$

This is a homogenous linear recurrence relation and can be solved in the standard way. Solving the recurrence relation reveals that this implementation of the Fibonacci runs in exponential time.

Observing that this defines recurrence relation also defines the Fibonacci sequence funnily implies that the runtime, \(T(n)\), of our function to calculate the value of the Fibonacci sequence at index \(n\) runs in \(O\left(F(n)\right)\) time where \(F\) refers to the value of the Fibonacci sequence at index \(n\).

However, the Fibonacci function is in fact primitive recursive. The primitive recursive solution comes about by noticing that every term of the Fibonacci sequence can be computed by only knowing the previous two values of the sequence.

So, define \(F’(n)\) to be \(\left< F(n), F(n+1) \right> \). We now have

$$ \begin{align} F’(0) &= \left<0, 1\right> \\ F’(1) &= \left<1, 1\right> \\ \end{align} $$

Since

$$ \begin{align} F’(n) &= \left< F(n), F(n+1)\right> \\ &= \left< F(n-1) + F(n - 2), F(n) + F(n - 1) \right> \\ &= \left< F’(n-1)_2, F’(n-1)_1 + F(n-1)_2 \right> \\ \end{align} $$

This is primitive recursive

$$ \begin{align} F(n) &= F’(n)_1 \\ \end{align} $$

The primitive recursive functions are closed under composition and ordered pairs can be represented using Gödel coding so the Fibonacci sequence is primitive recursive and the Fibonacci sequence can be calculated in \(O(n)\) time.

fib = fst . fib' where
  fib' 0 = (0, 1)
  fib' 1 = (1, 1)
  fib' n = (right, left + right) where
    (left, right) = fib' (n - 1)

1. Computability, Complexity and Languages, Davis, Sigal, Weyuker