A linear-space linear-time sequential recursive algorithm for evaluating a univariate polynomial (a polynomial of one variable) is the Horner scheme:
Function evaluate : (A, x) : y is, where a is the top of A,
- If A is empty, y is zero.
- Otherwise if A is a singleton, y is a.
- Otherwise, y is a + x * evaluate : (B, x), where B is A without a (the result of popping a from A).
