Rekursive Funktion baut sich auf und wieder ab

epistula

Hallo zusammen,

ich möchte einen rekursiven Algo programmieren, um die Rekursion besser zu verstehen. Der Algoritmus soll Zahlen von 1 bis n addieren und dann ausgeben. Die Funktion 'funct1' ruft sich dabei immer wieder selber auf, bis die 1 erreicht ist. Die Funktion funktioniert auch, das Problem ist nur, dass sie am Ende die addierten Zahlen wieder zurückzählt??? Das was sie schön zusammengerechnet hat, rechnet sie wieder schön zurück (Ein Mist). Ich find den Fehler nicht, seht ihr ihn?

Es geht um folgenden Algo:

---

#include <stdio.h>
#include <conio.h>

int Wert, Summe=0;

int funct1 (int n, int sum)
{
int summe;
if (n==1) {

sum+=1;
summe=sum;

} else {

sum+=n;
funct1(n-1, sum);
}
return summe;
}

int main()
{

printf("Geben sie n ein: ");
scanf("%d", &Wert);

funct1(Wert, Summe);
printf("Die Summe ist %d", funct1(Wert, Summe));
getch();

return 0;
}

---

CStoll

Wenn du die Funktion schon als int.. deklarierst, kannst du deine Ergebnisse auch per return zurückgeben.

(oder du definierst die Funktion als "int func1(int n,int& sum);" dann kann sie den übergebenen Parameter auch verändern)

CStoll schrieb:

Wenn du die Funktion schon als int.. deklarierst, kannst du deine Ergebnisse auch per return zurückgeben.

Das solltest du auf jeden Fall machen, da du sonst krampfhaft
versuchst, aus einer iterativen Funktion, eine Rekursive zu machen.

CStoll schrieb:

(oder du definierst die Funktion als "int func1(int n,int& sum);" dann kann sie den übergebenen Parameter auch verändern)

Das löst das Problem nicht.

Mal dir den Stack mal für n=2 auf; insbesondere solltest du auf
lokale Variablen achten!
Und wenn du schon dabei bist, dann pack mal Summe und Wert in
die main-Funktion.

Jockel

FireFlow

Ich glaube mal du wärst im C Forum besser aufgehoben, und ich glaube dass du das hier meinst:

unsigned sum(unsigned n)
{
    if(n == 0) {
        return 0;
    }
    else {
        return n + sum(n - 1);
    }
}

Gruß

int funct1 (int n, int sum)
{
    int summe;
    if (n==1) {

    sum+=1;
    summe=sum;

} else 
{

    sum+=n;
    funct1(n-1, sum);

}
    return sum;
} 
int main(int argc, char *argv[])
{
    int Wert, Summe=0;
    printf("Geben sie n ein: ");
    scanf("%d", &Wert);

    Summe=funct1(Wert, Summe);
    printf("Die Summe ist %d", funct1(Wert, Summe));
    getch();
}

ich weis zwar nicht ganz genau was du damit bezwecken willst aber versuchs dochmal so^^

MfG

Hast du es denn probiert?

Jockelx schrieb:

Mal dir den Stack mal für n=2 auf; insbesondere solltest du auf
lokale Variablen achten!
Jockel

Jockel

epistula

Hallo zusammen,

bin grad nach Hause gekommen. Ich probier es morgen früh mal aus und sag euch morgen mal die Ergebnisse.

An alle denen der Algo noch nicht ganz klar ist:

Angenommen n==5, dann ergibt sich sum aus sum=5. Bei den rekursiven Aufrufen wird n dann immer um 1 vermindert und zu sum addiert bis n==1 ist (also sum=5+4+3+2+1). Wenn n==1 ist soll dann diese Summe zurückgeliefert werden.

Das Programm soll also rekursiv die Summe von 1 bis n berechnen. Ich könnt den Algo ja mal debuggen, dann seht ihr mein Problem.

Aber wie gesagt, schon mal danke und ich probier eure Vorschläge morgen mal aus.

Gute Nacht!

CStoll

*folgt Jockel's Rat und verfolgt den Stack-Aufbau*

func(n=2,sum=0):
  sum+=n:sum=2
  func((n-1)=1,sum=2)
    func(n=1,sum=2)
      sum+=1:sum=3
      summe=sum:summe=3
      return sum:Rückgabewert 3
  Rückgabe von func(1,2) wurde ignoriert, Werte sind unverändert (Call by value)
  return sum:Rückgabewert 2

-> in main: Summe=2
printf()->func(n=2,sum=2):
  sum+=n:sum=4
  ...(siehe oben)
  ->Ausgabe 4

@epistula: Parameter werden immer per Wert übergeben, also kann die Funktion dort keine Änderungen nach außen übermitteln. Und da du die Rückgabe des rekursiven Aufrufes ignorierst, ist er im Endeffekt völlig wirkungslos.

epistula

Hallo zusammen,

dank eurer Hilfe hat es jetzt geklappt. Danke vor allem an FireFlow. So sieht der Algo jetzt aus:

-----

#include <stdio.h>
#include <conio.h>

int sum(int n)
{
if(n == 0) {
return 0;
}
else {
return n + sum(n - 1);
}
}

int main()
{
int wert;

printf("Geben sie n ein: ");
scanf("%d", &wert);

sum(wert);
printf("Die Summe ist %d", sum(wert));
getch();

return 0;
}

-----

Grüße!

epistula

Hallo zusammen,

ich hab doch noch eine Frage. Wie sehe 'int sum' eigentlich aus, wenn man ein Array nutzen möchte? Passt zwar jetzt nicht so ganz zu dem Algo, nur mal theoretisch. Geht das mit int sum[100](int n)? Wie löst man dann den Rücksprung?

Grüße!

Arrays kannst du nicht zurückgeben, nur Pointer auf dynamisch erzeugte Arrays ("r=new int[100];...return r;" - muß der aufrufende mit delete[] wieder freigeben) oder STL-Arrayklassen (vector,deque,valarray o.ä.).