Euler's Continued Fraction in Lisp

In 1748, Leonhard Euler published a formula describing an identity that connected and generalized an infinite series and infinite continued fraction. The continued fraction function can be defined as follows. Let n represent a numerator, d a denominator, and k a number of iterations. Upon each loop, our function will decrement its count and recurse on itself until reaching its iteration limit:

\begin{align*} \text{{cont-frac}}(n, d, k) = \begin{cases} \text{{result}} & \text{{if }} i = 0 \\ \text{{iter}}(i - 1, \frac{{n(i)}}{{d(i) + \text{{result}}}}) & \text{{otherwise}} \end{cases} \end{align*} .. where the iter function is defined as follows: \begin{align*} \text{{iter}}(i, \text{{result}}) = \begin{cases} \text{{result}} & \text{{if }} i = 0 \\ \text{{iter}}(i - 1, \frac{{n(i)}}{{d(i) + \text{{result}}}}) & \text{{otherwise}} \end{cases} \end{align*}

Altogether, courtesy of Wikipedia:

\begin{align*} {\displaystyle a_{0}+a_{0}a_{1}+a_{0}a_{1}a_{2}+\cdots +a_{0}a_{1}a_{2}\cdots a_{n}={\cfrac {a_{0}}{1-{\cfrac {a_{1}}{1+a_{1}-{\cfrac {a_{2}}{1+a_{2}-{\cfrac {\ddots }{\ddots {\cfrac {a_{n-1}}{1+a_{n-1}-{\cfrac {a_{n}}{1+a_{n}}}}}}}}}}}}}\,} \end{align*} To calculate the continued fraction using higher-order functions, such that our function accepts another function as input, we can use lambda functions, like so: \begin{align*} \text{{cont-frac}}(\lambda (i) 1.0, \lambda (i) 1.0, 10) \end{align*}

Putting it together, we can write this recursive function concisely in Lisp, with k defining the iterations or approximation accurary. We'll set it to 10.

(defun cont-frac (n d k)
  (labels ((iter (i result)
             (if (= i 0)
                 result
                 (iter (- i 1) (/ (funcall n i) (+ (funcall d i) result))))))
    (iter k 0)))

(format t "~a" (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 10))

Upon execution, the Lisp interpreter iterates ten times, then prints our result, 0.6179775.