= Solution
Keep the two adjacent <Fibonacci numbers> in one shared pair. From the <Fibonacci recurrence>, if the current pair is $(F_n,F_{n+1})$, the next is $(F_{n+1},F_n+F_{n+1})$. This gives the <paired Fibonacci recurrence>:
``
twoFibs :: Integer -> (Integer, Integer)
twoFibs 0 = (0, 1)
twoFibs n
| n > 0 = let (a, b) = twoFibs (n - 1)
in (b, a + b)
| otherwise = error "negative Fibonacci index"
fib :: Integer -> Integer
fib = fst . twoFibs
``
The pair pattern shares the result of the single <recursive call>. <Mathematical induction> establishes
$$
\boxed{\operatorname{twoFibs}(n)=(F_n,F_{n+1}),\qquad \operatorname{fib}(n)=F_n.}
$$
There are $n$ pair updates and $n$ <additions>, rather than the repeated subcomputations of the original branching <recursion>. This is linear arithmetic-operation count; exact <Fibonacci numbers> have growing bit length. The pattern `fib (n+2)` in the source expresses the recurrence; the guarded definition above uses ordinary <Haskell> syntax without requiring an `n+k` pattern extension.
Back to article page
