Rekursionen
-
Wenn du versuchst rekursiv zu arbeiten, dann musst du immer nur darüber nachdenken, wie das aktuell zu bearbeitende Element bearbeitest. Über die Berechnung aller vorherigen Elemente machst du dir keine Gedanken. Allerdings muss es immer mindestens ein Element geben, das gesondert behandelt wird.
Die Fakultät ist da ein schönes Beispiel. Die Fakultät von 0 ist 1. Das ist unser besonders zu behandelndes Element. Die Fakultät von einer belibigen anderen natürlichen Zahl (jaja, 0 ist keine natürliche Zahl, aber das ist jetzt mal egal) berechnet sich aus dem Produkt aus der Zahl und der Fakiltät aus der um 1 kleineren Zahl.
0! = 0
n! = n * (n-1)!Über das berechnen der Fakultät der nächst kleinere Zahl machst du dir einfach keine Gedanken. Du hast ja schon beschreiben, wie sich die Fakulät berechnen lässt. Dass dazu wiederum eine Fakultät nötig ist, interessiert nicht.
Das muss dann nurnoch in Code ausformuliert werden.unsigned fakultaet (unsigned n) { if (n==0) return 1; else return n * fakultaet (n-1); }Naja, C++ ist sicherlich nicht die schönste Sprache, um sowas zu Forumlieren.
Wenn du dich ernsthafter mit dem Thema Rekursion befassen willst, solltest du mal in eine funktionale Sprache reinschnuppern.fakultaet 0 = 0 fakultaet n = n * fakultaet (n - 1)
-
heliums beispiel ist gut:
der springende punkt ist eben, einen basisfall (bei fakultät i == 0) und einen rekursionsfall zu haben. der rekursionsfall führt immer einen schritt richtung basisfall. scheme oder prolog sind hier viel hübscher
%prolog fak(0, 1). %Fakultät von 0 ist 1 fak(N,F) :- N > 0, N1 is N-1, fak(N1,F1), F is N*F1. %bei N>0 solange 1 abziehen, biss man im basis fall ist, dann lösst sich alles in wohlgefallen auf :)
-
Danke für die vielen Posts!
-
@Korbinian: Du findest das Prologbeispiel tatsächlich schöner, als mein Haskell-Beispiel? Das kann ich jetzt nicht ganz nachvollziehen.
