Rekursions problem
lima-city → Forum → Programmiersprachen → C/C++ und D
aufruf
ausdruck
beitrag
beweis
compiler
fehler
funktion
gel
label
main
parameter
prozedur
register
rekursion
rekursiven variante
relativ
schleifen
variable
variante
zumindestens
-
ich m?chte mit folgender funktion n! berechnen, jedoch ist der r?ckgabewert nicht n! sondern (n-1)! wo liegt mein fehler?
int rec(int n)
{
if(n>1)
return n*rec(--n);
else
return 1;
}
void main()
{
cout<<rec(3)<<"\n";
}
//Der ausgegebene wert ist 3, ich m?chte jedoch 6 haben (3*2*1=6). auch klammern um n*rec(--n) helfen nicht.
Beitrag ge?ndert am 17.09.2005 22:14 von coderinside -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Postincrement statt Preincrement?
int rec(int n)
{
if(n>1)
return n*rec(n--);
else
return 1;
}
void main()
{
} -
Das schleift dann endlos:
da rec aufgerufen wird mit 3 und dann kommt das postincrement (rec(n--)) => was rec wieder mit 3 aufruft=>endlosschleife, da n erst nach der abarbeitugn der rekursieven funktion um eins verkleinert w?de... -
Mist, war doch nicht so einfach! Da muss ich wohl noch mal meine alten Postings durchforsten ...
*nachtr?glich_einf?g*
Das hier hab ich mal als PHP-Code geschrieben:
<?php
print("Fakult?t<br />n");
$zahl = 4;
$zahl2 = fak($zahl);
printf("Die Fakult?t von %s ist %s!<br />n", $zahl, $zahl2);
function fak($x) {
//printf("Berechne: %s<br />n", $x);
if($x == 1) return(1);
$y = fak($x - 1);
return($x * $y);
}
?>
?hm, in C?
int rec(int n)
{
if(n == 1)
return 1;
else
return n * rec(--n);
}
Hoffentlich hab ich das jetzt richtig ?bertragen ...
Irgendwie ist das auch dasselbe wie dein Code, oder?
Beitrag ge?ndert am 17.09.2005 22:50 von alopex -
Ich hoffe, dass ich deine Frage richtig verstanden habe. Warum nicht einfach mit einer Schleife:
int rec(int n)
{
int i = n;
while (i > 1 || i != 1)
{
n = n*(i-1);
i--;
}
return n;
} -
Ja, das geht auch ...
Naja, die Fakult?t ist das Paradebeispiel f?r die Rekursion beim Programmieren-Lernen. Da l?sst sich das ganze an einem noch relativ einfachen Problem ?berblicken. So hab ich es zumindest mal gelernt. Schleifen sind eher was f?r Weicheier.
Ok, wie w?re es, wenn man es mit Labels macht? Statt es in einer Schleife zu machen, kann man noch eine Variable dazu?bergeben oder sie global machen und st?ndig die Funktion nochmals aufrufen und wenn dann i = 1 dann ende.
Schleifen stellen doch heute keine Probleme dar, oder? Fr?her mit den Lochkartensystem war eine Schleife teuer und kostete Zeit. Was hast du gegen sie?
-
thx f?r die hilfe,
ich habe ?brigens ncihts gegen schleifen, sondern wollte mienem info lehrer beweisen, das schleifen schneller sind als rekursion, zumindestens bei fakult?t, ergebniss:
jede funktion(schleife/rekursiv) wurde 2^31-1 mal aufgerufen um die fakult?t von 25 zu bestimmen, die schleife hat 307.032 sec gebraucht, die rekursion 551.667 sec
ag noch mal jemand was von wegen schleifen seien f?r weicheier...
das ich (n-1) schreiben muss hab ich auch irgendwann gemerkt, aber wiso darf ich nicht(--n) schreiben? wirkt sich das dan auf das n davor(n*rec(--n) aus? -
Das Schleifen schneller sind als (rekursive) Funktionen liegt daran, dass bei jedem Funktionsaufruf mehr Pushs und Pops auf dem Stack gemacht werden m?ssen um die Funktionsparameter zu ?bergeben. Das dein Informatiklehrer da anderer Meinung ist/war finde ich sehr verwunderlich.
-
Pauschale Aussagen w?rde ich bei Compiler-Sprachen wie C lieber nicht machen. Man konnte fr?her auch mal Parameter an Prozeduren ?ber Prozessor-Register ?bergeben. Das hing von der Compiler-Konfiguration ab.
Interessant w?re auch mal ein Geschwindigkeitsvergleich mit meiner rekursiven Variante, die m?sste rein theoretisch langsamer sein, es sei denn der Compiler optimiert irgendwas weg.
Das Schleifen was f?r Weicheier sind, war nicht ganz ernst gemeint. Mir ging es mehr um den p?dagogischen Wert: Die (mathematische) Fakult?t ist ein sch?nes Beispiel, an dem man demonstrieren kann, wie man ein Problem rekursiv oder iterativ stellen und l?sen kann. Deswegen wird sie auch gern verwendet, wenn das rekursive Programmieren gelehrt wird. In der Praxis w?rde ich auch die Schleifen-L?sung vorziehen.
Der Unterschied zwischen "--n" und "n-1" will mir auch nicht in den Kopf. Da ich aber hier nur PHP zur Verf?gung habe, kann ich das nicht testen. Kann mal jemand mit C-Compiler die beiden Varianten durch einen Debugger laufen lassen oder die Variable "n" mal auf dem Bildschirm ausgeben lassen? W?rde mich mal interessieren, was da rauskommt.
MfG
alopex -
Ich bin zu faul um die Debugausgaben zu produzieren und hier in den Thread zu kopieren, aber ich habe folgendes in der OnlineHelp meiner IDE gefunden:
"In der Prefix-Variante findet das Inkrement oder Dekrement vor der Auswertung des Ausdrucks statt, somit unterscheidet sich der Wert im Ausdruck vom Wert des Operands."
D.h. also der Ausdruck
return n*(--n);
ist gleichbedeutend mit
return (n-1)*(n-1);
Beispielsweise w?rde
zahl = 7;
return zahl+(--zahl)*--zahl;
auch 42 ergeben. Ich hab' den Fehler auch nicht sofort bemerkt. Dachte deshalb jemand interessiert das evtl. noch...
Ade,
T. -
also, ich will ja nicht wieder eine verwirrende inkrement/dekrement diskussion eroeffnen, die gabs ja hier schon:
http://www.lima-city.de/boards.php?m=thread&id=31864
allerdings denke ich dass da ein fehler drin steckt:
zahl = 7;
return zahl+(--zahl)*--zahl;
auch 42 ergeben.
da zahl ja 2x vor ausfuehrung dekrementiert (sagt man das?) wird, muesste das doch
5+5*5, also 25 sein?
edit: wobei ja 42 eigentlich immer die richtige antwort ist
Beitrag ge?ndert am 21.09.2005 23:08 von keuloo -
haha, genaustens!
Du hast recht keuloo, da hab ich mich vertippt. So ein Scheif aber auch.
Es sollte nat?rlich zahl+(--zahl)*zahl, oder so ?hnlich heissen. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
