Mit dem Horner-Schema kann man Polynome auswerten. Dabei wird nur eine Addition und eine Multiplikation je Grad des Polynoms benötigt. Das Schema ist benannt nach William George Horner, einem englischen Mathematiker des 19. Jahrhunderts.

Eine mögliche Realisierung in Lisp ist die untenstehende Funktion. Diese erwartet drei Argumente:

- die Liste der Koeffizienten des Polynoms beginnend bei dem für den höchsten Grad und ohne Lücken,
- die Stelle, an der das Polynom ausgewertet werden soll und
- den Wert 0 als Startwert des Akkumulators.

Die Funktion prüft, ob die Liste der Koeffizienten leer ist. Wenn ja, dann wird der Akkumulator als Resultat geliefert. Anderenfalls ruft sich die Funktion rekursiv auf (siehe Rekursion). Dabei wird die Liste der Koeffizienten um den ersten verkürzt. Der Akkumulator wird mit der Stelle multipliziert, danach wird der erste Koeffizient addiert.

(defproc horner (coefficients x y)
  (if
    (null? coefficients)
    y
    (horner
      (rest coefficients)
      x
      (+ (first coefficients) (* x y)))))

Das Ergebnis eines Funktionsaufrufs ist der Wert des Polynoms an der angegebenen Stelle, wenn 0 als Startwert des Akkumulators verwendet wird.

Links
http://de.wikipedia.org/wiki/Horner-Schema
http://de.wikipedia.org/wiki/William_George_Horner