Rekursionen sind in Lisp (und damit auch in AutoLisp) von durchaus zentraler Bedeutung. Offensichtlich wird dieses Konzept aber von den meisten AutoLisp-Programmierern schlicht und einfach ignoriert. Deshalb befasst sich dieses Kapitel ausschliesslich damit, das Prinzip rekursiver Funktionen noch einmal vorzustellen und zu erläutern.

Das Standard-Beispiel für rekursive Arbeitsweise schlechthin ist die Funktion zur Berechnung der Fakultät einer Zahl, und auch ich werde es hier verwenden, da es wirklich wunderbar geeignet ist, die Zusammenhänge zu verdeutlichen. Zunächst einmal (für alle, die nicht wissen, was die Fakultät ist) eine kurze Erklärung:

Als Fakultät einer Zahl n bezeichnet man das Produkt aller Zahlen von 1 bis n. Schriftlich kennzeichnet man eine Fakultät, indem man ein Ausrufezeichen hinter die Zahl schreibt:

6! = 6 * 5 * 4 * 3 * 2 * 1 = 720

Und wozu braucht man das? Nehmen wir ein wenig technisches Beispiel: Wie viele Möglichkeiten gibt es für eine sechsköpfige Familie, am Esstisch mit sechs Stühlen Platz zu nehmen? Man ahnt die Antwort schon... Erstaunlich, dass (wenn man nur das Mittagessen betrachtet und davon ausgeht, dass jeden Tag eine andere Gruppierung gewählt wird) sich die Familie nur alle zwei Jahre in der gleichen Anordnung wiederfindet!

Um das Ganze nachvollziehbar zu machen: Der Erste, der sich am noch leeren Tisch niederlässt, kann zwischen 6 Stühlen wählen, der Zweite hat dann nur noch 5 Plätze zur Auswahl, was insgesamt nun schon 30 Möglichkeiten macht. Klar, dass das dritte hungrige Familienmitglied dann noch aus 4 Sitzplätzen auswählen kann (zusammen 120 Möglichkeiten) usw. usf.

Wesentlich ist die Erkenntnis, dass 7! das Siebenfache von 6! ist, oder anders ausgedrückt: Falls zum Essen noch ein Gast eingeladen ist, der einen Klappstuhl bekommt und sich (natürlich) als erster setzen darf, dann ändert sich doch an den Sitzverhältnissen der Familie absolut nichts! Es sind immer noch 6 Personen und 6 Stühle. Mit Gast haben wir also (7 * 720 = ) 5040 Möglichkeiten.

Kommen wir aber doch mal zum Programmieren: Genau diesen Denkansatz bauen wir in unsere Funktion ein: 7! ist das Siebenfache von 6!, das wiederum ist das sechsfache von 5!, was wiederum das fünffache .... Was ist eigentlich die Fakultät von 1? Die Fakultät von 1 ist 1, das ist einfach so! Ein Single mit einem einzigen Stuhl hat nun mal wenig Auswahl. Dies ist alles, was wir über die Fakultät wissen müssen. Unsere Funktion sieht so aus:

(defun fakultaet(zahl / )
  (if(= zahl 1)
    1
    (* zahl(fakultaet(1- zahl)))
  )
)
                  

Für jemanden, der sich noch nie mit Rekursionen auseinander gesetzt hat, mag es erstaunlich wirken, dass so etwas funktioniert - aber es funktioniert wirklich!

(fakultaet 6) => 720

(fakultaet 7) => 5040
                  

Allerdings hat die Funktion noch einen kleinen Schönheitsfehler: Sie sollte zunächst einmal testen, ob nicht eine negative Zahl eingegeben wurde - dafür ist die Fakultät nicht definiert! Und natürlich ist sie auch nur für ganze Zahlen gedacht, ein kleiner Umbau ist also noch fällig. Da die Zahlen übrigens sehr schnell sehr gross werden, fangen wir auch gleich mit ab, wenn eine zu grosse Zahl eingegeben wird: Mehr als 18! passen in einen 32-bit-Integer einfach nicht hinein, das sind immerhin 2.004.189.184 (eine 18-köpfige Familie würde also nur alle 5,5 Millionen Jahre in der gleichen Anordnung am Tisch sitzen!).

(defun fakultaet(zahl / )
  (setq zahl(fix zahl))
  (cond
    ( (> zahl 18) nil)
    ( (< zahl 1) nil)
    ( (= zahl 1) 1)
    (1(* zahl(fakultaet(1- zahl))))
  )
)
                  

Zugegeben, ein bisschen Lack ist abgeblättert - die erste Version war wesentlich eleganter und schlanker. Aber man muss sich entscheiden, ob man Eleganz oder Sicherheit vorzieht. Der Tempoverlust der zweiten Version wird sicherlich nicht ins Gewicht fallen, da die Rekursionstiefe ja recht beschränkt ist.

Um auch nochmal auf Zweifel einzugehen: Man kann die Arbeitsweise einer solchen Funktion sehr schon nachvollziehen, wenn man auf der AutoCAD-Kommandozeile ein (trace ...) absetzt. Die Ausgabe spricht für sich und bestätigt noch einmal all das, was hier besprochen wurde:

Befehl:(trace fakultaet)
Befehl: (fakultaet 6)
Eingabe von (FAKULTAET 6)
  Eingabe von (FAKULTAET 5)
    Eingabe von (FAKULTAET 4)
      Eingabe von (FAKULTAET 3)
        Eingabe von (FAKULTAET 2)
          Eingabe von (FAKULTAET 1)
          Ergebnis:  1
        Ergebnis:  2
      Ergebnis:  6
    Ergebnis:  24
  Ergebnis:  120
Ergebnis:  720
720
                  

Nun bleibt noch eine Frage: Gibt es eine Begrenzung für die Rekursionstiefe? Die Antwort ist ein eindeutiges Ja! Wir müssen damit leben, dass es einfach eine Grenze für die Verschachtelungstiefe von Funktionen gibt, unabhängig davon, ob diese rekursiv aufgerufen werden oder nicht. Dazu gleich noch eine Testfunktion hinterher:

(defun tiefe-test(arg / )
  (princ arg)
  (princ "\n")
  (tiefe-test(1+ arg))
)
                  

Diese Funktion, aufgerufen mit 1 als Argument, bricht nach der Ausgabe von 19996 ab (AutoCAD 2000i). Ich weiss nicht, wie es sich mit anderen AutoCAD-Versionen verhält, und ebenso wenig, ob andere Faktoren evtl. eine Rolle spielen. Auf jeden Fall bietet die mögliche Rekursionstiefe aber genügend Spielraum, eine Behinderung sollte sie jedenfalls nicht darstellen.