= Solution
Use the <Euclidean algorithm> with floor quotient and nonnegative remainder, including for a negative numerator:
``
PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR q, r: INTEGER; p: fraction;
BEGIN
q := n DIV d; r := n MOD d;
NEW(p); p.head := q; p.tail := NIL;
IF r # 0 THEN p.tail := rat2cf(d, r) END;
RETURN p
END rat2cf;
``
For $d>0$, <Euclidean division> gives $n=qd+r$ with $0\leq r<d$. If $r=0$, the singleton `[q]` is exact. Otherwise
$$
\frac nd=q+\frac rd=q+\frac1{d/r},
$$
so the recursive tail represents $d/r$. Its numerator is positive and greater than its denominator, so every tail head is a positive <integer>. The new denominator $r$ is strictly smaller than $d$, proving <algorithm termination> by descent through the positive <integers>.
\b[The returned list represents exactly $n/d$.] For example $-7/3=-3+1/(1+1/2)$ gives `[-3,1,2]`; truncating negative division toward zero would violate the required positivity of the tail. There are $O(\log d)$ <Euclidean algorithm> steps, with output allocation and recursive stack depth linear in the number of generated nodes.
Back to article page
