Rekursion
-
Hi erst mal an alle
Habe ein Problem mit Rekursion:
Ich möchte eine Funktion schreiben welche mir die Summe von 1 bis zu der übergebenen Zahl berechnet,,zusätzlich soll jede Zahl quadriert werden,,
Also wenn der Parameter 3 wäre:(1*2)+(2*2)+(3*2)=12
Nun bin ich dabei einen passenden Algorithmus zu formulieren,,und zwar rekursiv:
Leider ist das nicht so einfach wie ich dachte,,meine beiden Lösungsansätze sehen wie folgt aus:
int func(int n)
{
if(n>0) n+=2*(func(n-1));
return n;
}int func(int n)
{
if(n>0) n+=func(n-1);
return n*2;
}Beide Funktion liefern unterschiedliche, jedoch falsche Ergebnisse,,
Wo liegt da mein Denkfehler??
-
1. In Deinem Beispiel quadrierst Du nicht sondern multiplizierst mit 2. Quadrieren wäre:
(1*1) + (2*2) + (3*3) + ...
Das sieht irgendwie nicht sehr rekursiv aus...2. Dein Algorithmus 1 liefert
(für n = 2):
2 + 2 * ( 1 + 2 * 0)
(für n = 3):
3 + 2 * ( 2 + 2 * ( 1 + 2 * 0)))3. Dein Algorithmus 2 liefert:
(für n = 2):
(2 + ( 1 + 0 * 2) * 2) * 2
(für n = 3):
(3 + ( 2 + (1 + 0 * 2) * 2) * 2) * 2
-
AJ_Styles schrieb:
zusätzlich soll jede Zahl quadriert werden,,
Also wenn der Parameter 3 wäre:(1*2)+(2*2)+(3*2)=12
Das ist nicht Quadrieren, das ist einfaches Multiplizieren mit 2.
Wo liegt da mein Denkfehler??
Vollzieh doch mal auf dem Papier nach, was da z.B. bei 3 passiert. Dann siehst du, warum das nicht funktionieren kann.
n += ist schon mal ein merkwürdiger Ansatz. In deiner Formel steht nirgends 3+. Das erste, was mit n gemacht wird, ist eine Multiplikation.
-
Danke erstmal,,
mit anderen Worten: Problem eher iterativ lösen,,
-
AJ_Styles schrieb:
mit anderen Worten: Problem eher iterativ lösen,,
Nö, wieso? Das klappt auch rekursiv. Gib doch nicht gleich auf
-
Also ich würde folgenden Ansatz nehmen
1\*a+2\*a+3\*a+...+n\*a =a(1+2+3+...+n) =\frac{a\*n\*(n+1)}{2}Wenn du da aber umbedingt eine Rekursion reinquetschen willst dann bleibt dir wohl nur das ganze mit einer als Endrekursion formulierten Schleife auszudrücken.
-
Ich glaub ich lass es lieber sein
Eine Frage noch: Auf wieviel MB ist der Stack unter XP begrenzt?? Gibt es eine Möglichkeit die Stackgröße in Visual C++ zu ändern??
-
Standardmäßig wird eine Größe von 1MB allokiert. Das lässt sich über einen Compiler- bzw. Linkerswitch festlegen oder auch zur Laufzeit ändern. Wenn du einen neuen Thread erstellst, kannst du ja zum Beispiel direkt die Stackgröße dafür definieren.
-
double func(double n) { if(n<=1) return 1; return pow(n,2) + func(n-1); }
-
Schön, wenn wir nun das pow noch eliminieren und wieder Ganzzahlen daraus machen, könnte der OP sicher damit leben.
-
Funktioniert!!
Danke an alle,,
-
sorry... wer ist OP?
int func(int n) { if(n <= 1) return 1; return (n * n) + func(n - 1); }
-
prokaion schrieb:
sorry... wer ist OP?
OP == Orginal Poster == AJ_Styles
<korintenkack>
int func(int n) { if(n <= 1) return 1; return (n * n) + func(n - 1); }Ich glaube der OP wollte garnicht quadrieren, sondern einfach nur mit 2 multiplizieren
</korintenkack>Gruß Caipi
-
So siehts aus
Da hab ich mich wohl vertippt
-
Soso, mit 2 multiplizieren, hm,
na dann hab ich den ganzen code wohl umsonst geschrieben....
schnauf!
-
prokaion schrieb:
Soso, mit 2 multiplizieren, hm,
na dann hab ich den ganzen code wohl umsonst geschrieben....
schnauf!warum heulst du deswegen gleich?? man war doch nicht viel code!! komm mal wieder klar.
-
cmnt. schrieb:
prokaion schrieb:
Soso, mit 2 multiplizieren, hm,
na dann hab ich den ganzen code wohl umsonst geschrieben....
schnauf!warum heulst du deswegen gleich?? man war doch nicht viel code!! komm mal wieder klar.
ich hoffe das meinst du nicht ernst xD
-
ihr habt das echt ernst genommen? 2 zeilen code??
und wo man aus dem n nur ne 2 machen muss??natürlich war das NICHT ernst gemeint!!!
(nochmal für alle: NEIN, DASWARNICHTERNSTGEMEINNNNT!!
)mfg
-
Danke Prokaion,,
aber eigentlich müsste es heißen: if(n <= 1) return 2;
-
uups! wohl wahr