Die Fakultät einer natürlichen Zahl n ist das Produkt der ersten n Zahlen:

n! = 1 * 2 * 3 * ... * (n-1) * n

Möchte man etwa 5! berechnen, so müssen die Zahlen von 1 bis 5 multipliziert werden. Hätte man schon zuvor die Fakultät von 4 ermittelt, so würde es ausreichen, diese noch mit 5 zu multiplizieren.

Der rekursive Ansatz greift den letzten Gedanken auf:

n! = n * (n-1)!

Das Ganze hat nur einen Haken: Diese Rechenvorschrift bricht nie ab, auch wenn der Term (n-1) irgendwann negativ wird.  Wir benötigen also noch einen Stoppfall:

Wenn n=1 ist, dann bricht diese berechnung ab und nimm 1! =1.

Damit erhält man folgende rekursive Rechenvorschrift:

 -- Rekursive Berechnung der Fakultät
 f (1) = 1
 f (n) = n * f (n-1)

Exakt in dieser Form kann man die Fakultät auch in Haskell definieren. Üblicherweise verwendet man die Klammerfreie Darstellung:

 -- Rekursive Berechnung der Fakultät in der klammerfreien Darstellung
 f 1 = 1
 f n = n * f (n-1)

Die Folge der Fibonaccizahlen 1,1,2,3,5,8,13,... wird durch folgende Vorschrift definiert: 

Die ersten beiden Fibbonaccizahlen sind 1 und 1. Zur Berechnung der n. Zahl muss man die beiden Vorgängerzahlen addieren. Diese können nur dann berechnet werden, wenn deren Vorgänger bekannt sind, usw. Irgendwann kommt man dann auf die beiden Stoppfälle zurück. 

  -- Die Fibbonaccifunktion
  a (1) = 1
  a (2) = 1
  a (n) = a (n-1) + a (n-2)

Zur Berechnung der n. Fibonaccizahl ersetzt der Rechner die einzelnen Terme durch ihre jeweilige Definition. Dadurch bläht sich der Term zunächst stark auf, bevor er durch konkrete Berechnungen wieder kleiner wird.

  a(4) = a(4-1)          + a(4-2)
       = a(3)            + a(2) 
       = a(3-1) + a(3-2) + 1 
       = a(2)   + a(1)   + 1 
       = 1      + 1      + 1 
       = 2      + 1
       = 3

Die Auswertung der Fakultät zeigt noch deutlicher das Aufblähen und Schrumpfen rekursiver Berechnungen:

  -- Auswertung der Fakultät 5!
  f (5) = 5 * f(4)
        = 5 * 4 * f(3)
        = 5 * 4 * 3 * f(2)
        = 5 * 4 * 3 * 2 * f(1)
        = 5 * 4 * 3 * 2 * 1
        = 5 * 4 * 3 * 2
        = 5 * 4 * 6
        = 5 * 24
        = 120