Das Pascal’sche Dreieck ist ein offensichtliches Beispiel für Rekursion. Ausgehend von einer Dreiecksspitzen können neue Zeilen aus der letzten Zeile erzeugt werden. Jede neue Zeile erhält eine Zelle mehr - damit ergibt sich daraus ein Dreieck.

 

Die Zahlen werden jeweils aus der übergeordneten Zeile ermittelt. Das Randfeld erhält den Wert 1. Die inneren Felder berechnen sich aus der Summe der Werte aus der vorgehenden Zeile.

In mathematischer Notation ist das Pascal’sche Dreieck folgendermaßen definiert:

Wobei n die aktuelle Zeile und k die aktuelle Spalte angibt.