Faktoriell aufrufen

Kuldren

StefanR. schrieb:

Ich würde gern ein Programm schreiben was von einer zahl die ich eingebe die faktorielle ausrechnet und zwar hab ich gehört geht das mit einem Unterprogramm das sich selbst aufruft.

Hab da jetzt schon ziemlich lange überlegt aber ich komm nicht drauf wie ich das Unterprogramm amchen soll damit es sich selbst aufruft

Ich bitte euch mir da aus der Patsche zu helfen

Thx

Ohne ein Beispiel ist Rekursion am Anfang nicht so einfach zu verstehen.
Sieh dir das an und denk es durch:

int fakt(int x){

	if(x>=2)
		return x*fakt(x-1);
	else
		return 1;

}

int main(){
...
fakt(Zahl);
}

EDIT: Kopierfehler ausgebessert

Wirdbald

Wo es einfach möglich ist, solltest Du aber unbedingt auf rekursive Funktionsaufrufe verzichten. Es ist nicht sonderlich performant, weil die äußere Funktion immer "offen" bleibt, wenn sie in sich selbst noch einmal aufgerufen wird. D.h. jede laufende Instanz einer Funktion erfordert einen Eintrag auf dem Call-Stack. Und der ist im Extremfall irgendwann voll und dein Programm stürzt ab. Das könnte vielleicht bei der Berechnung einer großen Fakultät passieren.
Nicht-rekursiv geht es etwa so:

int fakt(int x){
  if(x<2)
    return 1;

  int f = 1;
  for(int i = 2; i <=x; ++i)
  {
    //Achtung: hier kann es auch zu überraschenden Ergebnissen kommen,
    //weil die Zahl nicht mehr in einen int passt ;-)
    f *= i;
  }

  return f;
}

Edit:
Returnwert für x<2 korrigiert. Falls das nochmal jemand abschreibt. (und vielleicht den Datentyp in uint64_t oder etwas ähnliches ändert)

Nexus

Wirdbald schrieb:

Und der [Call-Stack] ist im Extremfall irgendwann voll und dein Programm stürzt ab. Das könnte vielleicht bei der Berechnung einer großen Fakultät passieren.

Naja, mit einer Fakultät wird man viel früher an die Grenzen der Datentypen stossen.

Bereits ab 13! passt die Zahl in keinen int mehr. Die Fakultät wächst unglaublich schnell, da muss man sich überlegen, ob man es nur zum Ausprobieren macht und einem die ersten paar Werte reichen.

Kuldren

Nexus schrieb:

Wirdbald schrieb:

Und der [Call-Stack] ist im Extremfall irgendwann voll und dein Programm stürzt ab. Das könnte vielleicht bei der Berechnung einer großen Fakultät passieren.

Naja, mit einer Fakultät wird man viel früher an die Grenzen der Datentypen stossen.

Bereits ab 13! passt die Zahl in keinen int mehr. Die Fakultät wächst unglaublich schnell, da muss man sich überlegen, ob man es nur zum Ausprobieren macht und einem die ersten paar Werte reichen.

Das ihr hier aber auch alles verraten müsst...

Nexus

Kuldren schrieb:

Das ihr hier aber auch alles verraten müsst...

Was meinst du?

Bashar

Kuldren schrieb:

Sieh dir das an und denk es durch:
int fakt(int x){

	if(x>=2)
		return x*fakt(x-1);
	else
		return x;

}

Deine Funktion ist falsch: 0! = 1, bei dir 0

Nexus

Bashar schrieb:

Deine Funktion ist falsch: 0! = 1, bei dir 0

Naja, sprechen wir jetzt mal nicht über negative Argumente...

Kuldren

Bashar schrieb:

Kuldren schrieb:
Sieh dir das an und denk es durch:
int fakt(int x){

	if(x>=2)
		return x*fakt(x-1);
	else
		return x;

}
Deine Funktion ist falsch: 0! = 1, bei dir 0

Stimmt...tut leid

Muss

int fakt(int x){

    if(x>=2)
        return x*fakt(x-1);
    else
        return 1;

}

lauten...habs beim reinkopieren vergessen

Naja, sprechen wir jetzt mal nicht über negative Argumente...

Ja...sprechen wir jetzt mal nicht von der grafischen Ausgabe...

Ist klar dass das nur mit positiven Argumenten ausgeführt wird.
Aber wenn du willst darfst du eine Precondition schreiben

Bashar

Nexus schrieb:

Bashar schrieb:

Deine Funktion ist falsch: 0! = 1, bei dir 0

Naja, sprechen wir jetzt mal nicht über negative Argumente...

Da die Fakultät für n<0 nicht definiert ist, ist das höchstens eine Frage der Robustheit.

Wirdbald schrieb:

Wo es einfach möglich ist, solltest Du aber unbedingt auf rekursive Funktionsaufrufe verzichten. Es ist nicht sonderlich performant, weil die äußere Funktion immer "offen" bleibt, wenn sie in sich selbst noch einmal aufgerufen wird. D.h. jede laufende Instanz einer Funktion erfordert einen Eintrag auf dem Call-Stack. Und der ist im Extremfall irgendwann voll und dein Programm stürzt ab. Das könnte vielleicht bei der Berechnung einer großen Fakultät passieren.

Die Argumentation über Performance ist schwierig, hier sogar falsch, da ein ordentlicher Compiler hier die Rekursion eh eliminieren wird.

Kuldren schrieb:

Ist klar dass das nur mit positiven Argumenten ausgeführt wird.
Aber wenn du willst darfst du eine Precondition schreiben

Oder nur positive Argumente zulassen indem man den angemessenen Datentyp nimmt - wozu gibts unsigned int?

Kuldren

pumuckl@loggedoff schrieb:

Kuldren schrieb:

Ist klar dass das nur mit positiven Argumenten ausgeführt wird.
Aber wenn du willst darfst du eine Precondition schreiben

Oder nur positive Argumente zulassen indem man den angemessenen Datentyp nimmt - wozu gibts unsigned int?

In dem Fall ein klares NEIN

Ich würde generell eher darauf verzichten ...
Mit unsigned int einfach das Vorzeichen zu kicken würde zwar die Funktion zum Teil erfüllen aber dafür sicher einige Fehler zur Folge haben, denn 1. ist die Fakultät für negative Zahlen undefiniert und 2. hat es sicher einen Grund warum negative anstatt positive Argumente übergeben werden - was in den meisten Fällen sicher ein Fehler im Programm ist.
Hier also unsigned int zu verwenden ist nichts anderes als schlechter Programmierstil....
Wofür gibts Conditions?

Fellhuhn

Oder exceptions...

Endrekursion bietet sich hier aber auch eher an. Also den rekursiven Aufruf an das Ende der Funktion mit dem return verknüpfen. So sollte, wenn der Compiler das kann, der Stack wiederverwendet werden. Wobei ich aber gerade nicht weiß ob C++ das überhaupt kann.

Kuldren

Ich finds immer wieder witzig wie hier einfachste Beispiele, die wie in diesem Fall nur einmal das Thema Rekursion einfach aufzeigen sollen an allen möglichen Ecken beanstandet werden

(Mal abgesehen von dem Fehler beim Reinkopieren ist der Rest sinnlos.)
Als nächstes kommt einer daher und will mit ein paar Funktionen sicherstellen dass das richtige Betriebssystem vorhanden ist, die Systemzeit stimmt und welche Compilerversionen vorhanden sind.

Es ist anhand der Definition der Fakultät ersichtlich dass nur Argumente >=0 zugelassen sind, da braucht es keine Exceptions, Preconditions, Vorzeichen kicken oder sonstwas...
Ist aber echt lustig - anstatt es direkt so zu programmieren wie es gehört wird lieber an allen Ecken und Enden gecastet, Exceptions geworfen oder sonstwas gemacht anstatt direkt sicherzustellen dass nichts anderes als die zugelassenen Parameter übergeben werden.

Wer jetzt mit "aber man muss sicherstellen dass es keine Fehler gibt" ankommt:
Das ist in dem Fall egal - wer es nicht bemerkt hat...ich hab in main auch Drei punkte reingebastelt, um den fehlenden Code zu symbolisieren...wenn man das aber direkt so einbindet wirft das einen Fehler... Oh nein...
Die header hab ich auch vergessen...
Ehrlich...

Fellhuhn

Kuldren schrieb:

Mimimimi

Habs für dich zusammengefasst.

Kuldren

Fellhuhn schrieb:

Kuldren schrieb:

Mimimimi

Habs für dich zusammengefasst.

Hat dir den Witz heute einer in der Volksschule erzählt und du musstest es gleich im Internet ausprobieren?

Fellhuhn

Kuldren schrieb:

Fellhuhn schrieb:

Kuldren schrieb:

Mimimimi

Habs für dich zusammengefasst.

Hat dir den Witz heute einer in der Volksschule erzählt und du musstest es gleich im Internet ausprobieren?

Da hatten wir nur Singen und Klatschen.

Kuldren

Fellhuhn schrieb:

Kuldren schrieb:

Fellhuhn schrieb:

Kuldren schrieb:

Mimimimi

Habs für dich zusammengefasst.

Hat dir den Witz heute einer in der Volksschule erzählt und du musstest es gleich im Internet ausprobieren?

Da hatten wir nur Singen und Klatschen.

Ist klar...die wollen ja Niemanden überfordern

Fellhuhn

Kuldren schrieb:

Fellhuhn schrieb:

Kuldren schrieb:

Fellhuhn schrieb:

Kuldren schrieb:

Mimimimi

Habs für dich zusammengefasst.

Hat dir den Witz heute einer in der Volksschule erzählt und du musstest es gleich im Internet ausprobieren?

Da hatten wir nur Singen und Klatschen.

Ist klar...die wollen ja Niemanden überfordern

Hatte ne 5.

Nexus

@ Kuldren:
Wieso regst du dich so darüber auf, dass dein Programm "kritisiert" wird? Erstens sind die anderen Argumente als das von Bashar (inklusive meinem) nicht als Vorwurf zu interpretieren. Ich habe es übrigens auch nicht ganz ernst gemeint, und Fellhuhn scheinst du auch noch nicht zu kennen. Andernfalls kann ich mir deine Reaktion wirklich nicht erklären...

Und wenn du unsere Reaktionen sowieso schon vorhergesehen hast, wieso hast du dann überhaupt gepostet?

Tim schrieb:

da ein ordentlicher Compiler hier die Rekursion eh eliminieren wird.

Werden Rekursionen vom Compiler auch optimiert? Es gibt ja einige Fälle, wo eine iterative Lösung gar nicht unbedingt besser und auch nicht einfacher zu realisieren ist.