Doppeltes Return und Return als Multiplikator (C)

[ScoutX]

/* fakul.c */
#include <stdio.h>
#include <stdlib.h>

long fakul(long n) {
   if(n){
      return n * fakul(n-1);
   }
   return -2*(3+2);
}

int main(void) {
   printf("Fakultät von 4 = %ld\n",fakul(4));
   printf("Fakultät von 9 = %ld\n",fakul(9));
   return EXIT_SUCCESS;
}

Beispiel anhand der Fakultätsberechnung:
Warum wird das zweite Return in der Rekursion als Multiplikator genutzt?

 

[HominiLupus]

Warum nicht?
Es ist eine rekursive Fakultätsberechnung. Wie sonst sollte man es machen damit diese auch abbricht wenn n==0?

 

[Mika911]

Mal sollte erwähnen, dass die Methode mit erreichen eines "return" bereits beendet wird.
Das 2. return wird nur ausgeführt, wenn n == 0.

 

[asdfman]

Verstehe die Frage nicht, aber versuche mal zu erklären, was passiert. Return wird nur einmal abgearbeitet, wenn man das erste Mal darauf trifft. Wenn die Bedingung erfüllt ist, wird der erste Ausdruck zurückgegeben und die Funktion ist an dieser Stelle beendet. Wenn die Bedingung nicht erfüllt ist, trifft das Programm erst am Ende der Funktion auf das return-Statement und nur dieses wird abgearbeitet.

Was den Ausdruck hinter dem zweiten return-Statement angeht, erschließt sich mir der Sinn nicht, denn erstens ist der zurück zu gebende Ausdruck konstant, man könnte die Berechnung da einfach durch ihr Ergebnis ersetzen und zweitens erhält man damit keine korrekte Fakultätsfunktion, denn die Fakultät von 0 (die dort zurück gegeben werden soll) hat den Wert 1 und nicht -10 (das Ergebnis des Ausdrucks "-2*(3+2)")

 

[Freezedevil]

Was den Ausdruck hinter dem zweiten return-Statement angeht, erschließt sich mir der Sinn nicht, denn erstens ist der zurück zu gebende Ausdruck konstant, man könnte die Berechnung da einfach durch ihr Ergebnis ersetzen und zweitens erhält man damit keine korrekte Fakultätsfunktion, denn die Fakultät von 0 (die dort zurück gegeben werden soll) hat den Wert 1 und nicht -10 (das Ergebnis des Ausdrucks "-2*(3+2)")

Danke, ich dachte schon ich wäre vollkommen verrückt.

Desweiteren sollte man noch anmerken, dass die Funktion so etwas gefährlich ist. Wird die Funktion mal, wodurch auch immer, mit nem negativen Wert aufgerufen, wird sich dein Programm ziemlich schnell verabschieden.

 

[asdfman]

Desweiteren sollte man noch anmerken, dass die Funktion so etwas gefährlich ist. Wird die Funktion mal, wodurch auch immer, mit nem negativen Wert aufgerufen, wird sich dein Programm ziemlich schnell verabschieden.

Nicht nur dann, aber das sind Details, die den Sinn der Übung verfehlen und deshalb erstmal vernachlässigt werden sollten. Was nützt es, jemanden mit Limitierungen des Systems zu überfordern, wenn es darum geht, das Konzept der Rekursion rüberzubringen? Man lernt ja auch nicht in der Chemie der 5. Klasse Orbitaltheorie.

 

[ScoutX]

Was den Ausdruck hinter dem zweiten return-Statement angeht, erschließt sich mir der Sinn nicht, denn erstens ist der zurück zu gebende Ausdruck konstant, man könnte die Berechnung da einfach durch ihr Ergebnis ersetzen und zweitens erhält man damit keine korrekte Fakultätsfunktion, denn die Fakultät von 0 (die dort zurück gegeben werden soll) hat den Wert 1 und nicht -10 (das Ergebnis des Ausdrucks "-2*(3+2)")

Die Fakultätsfunktion wäre korrekt mit dem Wert return 1.
Zur Veranschaulichung habe ich das Beispiel verfremdet. Ich wollte nur wissen warum die Rekursion mit der Multiplikation des zweiten Return (1 = korrekt für Fakultät; jeder andere beliebige Wert oder sogar Gleichung auch einsetzbar) endet.

Ergänzung: Als Beispiel würde für Return -10 bei dem Wert 4 eben -240 erhalten werden. Mir ist nicht klar, warum bei dem Wert n == 0 noch eine weitere Multiplikation stattfindet, da die If-Schleife schon verlassen wurde.

 

[Freezedevil]

Bei jedem Funktionsaufruf wird die Funktion selbst wieder aufgerufen. Der "Aufrufer" bleibt dabei solange "geöffnet" bis das Ergebnis seines Aufrufes vorliegt. Das passiert solange nicht der Basisfall eingetreten ist. In diesem wird nämlich kein neuer Aufruf gestartet, sondern erstmalig ein Ergebnis zurückgeliefert. Das setzt sich dann noch oben fort.
Edit: Tatsächlich ist die Rekursion beim erreichen des Basisfalls nicht beendet, sondern die Berechnung beginnt im Grunde genommen erst dort. Die Arbeit wird beim sogenannten Rekursiven Aufstieg erledigt. Es gibt auch Rekursionen die ihre Arbeit schon beim Abstieg erledigen und beim Erreichen des Basisfalls tatsächlich fertig sind.

fak(4)

4*fak(3)
  3*fak(2)
    2*fak(1)
      1*fak(0)
        1
      1*1=1
    2*1=2
  3*2=6
4*6=24  <--Ergebnis

@asdfman: Du hast sicher Recht, aber man sollte sich wenigstens Gedanken darüber machen, sonst macht man irgendwann Murks. In welchen Fällen geht das noch schief? Oder meinst du nur, wenn das Ergebnis zu groß für nen long wird?

 

[asdfman]

Ich bin hier am Telefon, deshalb gibt es sicher schon 10 neue Antworten, wenn ich auf Absenden drücke, aber dennoch:

Eine der wichtigsten Aufgaben bei der Programmierung ist es, gemeinsame Muster zu erkennen und diese zu verallgemeinern. Ein Beispiel mit konkreten Werten:

3! = 1*2*3
2! = 1*2
1! = 1

Das gemeinsame Muster ist hier, dass die Fakultät einer positiven ganzen Zahl n gleich der Fakultät der nächst kleineren Zahl mal n ist. Man kann das Problem, die Fakultät von n zu berechnen auf das einfachere Problem, die Fakultät von n-1 zu berechnen reduzieren:

n! = (n-1)! * n

Das macht man so lange weiter, bis man bei einem trivialen Fall (0!=1) angekommen ist. Diese Erkenntnis schlägt sich in dem Programm so nieder:

Ist n = 0? Wenn ja, ist das Ergebnis 1 und wir sind fertig.
Ansonsten merken wir uns n und schieben das Problem weiter und lassen erstmal (n-1)! ausrechnen. Wenn wir das mit n multiplizieren, haben wir die gewünschte Lösung und sind auch fertig.

Den letzten Schritt wiederholt man so oft, bis man beim "einfachen" Fall (n=0) angekommen ist und das Ergebnis an die nächst höhere Ebene zurückgegeben kann. Die hat sich die 1 gemerkt und 1 als Ergebnis zurück bekommen. Also ist 1! = 1 und das wird weiter gesagt. Der nächste hat sich die 2 gemerkt, also ist 2! = 2 * 1. Undsoweiter bis man beim ursprünglichen n angekommen ist.

Hoffe, das war eine nachvollziehbare Erklärung.

Ergänzung (9. Januar 2014)

Freezemann: Meinte auch, wenn n zu groß für den Call stack wird.

 

[ScoutX]

Danke. Ich hatte für den rekursiven Aufstieg bzw. in der Stapelverarbeitung mich irgendwie auf die Idee fixiert, dass das letzte Return ausserhalb der If-Schleife separat abgearbeitet werden muss, da es eben ausserhalb der If-Schleife liegt. Kompletter Gedankenfehler.

P.S. Das Beispiel wurde entnommen aus dem Open-Book von Galileo für C-Programmierung.

 

[Freezedevil]

Gewöhn dir bitte schnell wieder ab If-Schleife zu sagen, bevor sich das einschleift (dafür komme ich in die Wortspielhölle). Es gibt nur Schleifen und If-Anweisungen

 

[asdfman]

Und wenn Frostie schon korrigiert, will ich auch!

"return -2*(3+2);" ist keine Gleichung. Nicht nur aus dem offensichtlichen Grund, dass kein Gleichheitszeichen vorkommt. Auch ein Ausdruck wie "x = 2 * 9" hat nichts mit einer Gleichung zu tun, wie man sie aus der Algebra kennt. Zum Beispiel:

a = 10
a = 24

Wenn man diese zwei Zeilen als algebraische Gleichungen betrachtet, sind sie widersprüchlich und sinnlos. Die Variable a kann nicht gleichzeitig 10 und 24 sein. In Programmiersprachen wie C sind sie aber völlig eindeutig und haben einen Sinn, denn es sind verschiedene Zuweisungen, die in einem zeitlichen Ablauf erfolgen. In der Algebra müssen aber alle Gleichungen gleichzeitig gültig sein.

€: Auch etwas wie "if(a == 42)" ist keine Gleichung, denn a kann ja auch den Wert 23 haben. Gewöhne dir für Ausdrücke einfach den Begriff "Ausdruck" an. Das schließt Gleichungen mit ein, aber du kannst trotzdem nicht falsch liegen, wenn es eigentlich keine ist, sondern eine Zuweisung oder ein Vergleich.