= Solution
Convert the tail first and apply the reciprocal identity. Two output parameters hold the <rational number>'s numerator and denominator.
``
PROCEDURE cf2rat(f: fraction; VAR n, d: INTEGER);
VAR u, v: INTEGER;
BEGIN
IF f.tail = NIL THEN
n := f.head; d := 1
ELSE
cf2rat(f.tail, u, v);
n := f.head * u + v;
d := u
END
END cf2rat;
``
The singleton case is immediate. If the recursive call returns the tail as $u/v$, then $u,v>0$ because every tail head is positive. The full value is
$$
f.\mathrm{head}+\frac1{u/v}=\frac{f.\mathrm{head}\,u+v}{u}.
$$
<Structural induction> on the finite nonempty <linked list> proves correctness, and the denominator is always positive even if the first head is negative. If the tail pair is coprime, then $\gcd(xu+v,u)=\gcd(v,u)=1$; the base pair $(x,1)$ is coprime, so the result is in lowest terms. \b[Return `(head*u+v,u)` after converting the tail], using linear node-processing time and linear recursive stack space.
Back to article page
