Rekursion in C, Programm stürzt ab. Wo ist der Fehler ?

[ThE_sMoKeY_jOe]

Hi,

mach gerade ein paar Programmier Übungen als Prüfungsvorbereitung, es geht um Rekursion, kein besonders kompliziertes Programm eigentlich.

Es sollen eingegebene Zahlen nacheinander subtrahiert und addiert werden, allerdings stürzt ein Programm nach der Eingabe der Zahlen ab, sitze jetzt schon ein weilchen mit meinem Kumpel davor aber wir finden den Fehler nicht, hoffe ihr könnt mir helfen .

Danke.

#include<stdio.h>

int subadd(int zahlen[], int n, int erg, int i)
{
  while((n-1)<=i)
  {
      if(n-1%2==0)
      {
        erg=erg+zahlen[n-1];
      }
      else
      {
        erg=erg-zahlen[n-1];
      }
        subadd(zahlen, n++, erg, i);
  }
  return erg;
}

int main(void)
{
  int zahlen[100], ergebnis=0, i, n;

  printf("\nAnzahl der Zahlen:");
  scanf("%d", &n);
  printf("\nBitte die Zahlen mit Leerzeichen getrennt eingeben:");
  for(i=0; i<n; i++)
  {
    scanf("%d", &zahlen[i]);
  }
  n=n-(n-1);
  printf("\nDas Ergebnis ist:%d", subadd(zahlen, n, ergebnis, i));


}

Danke für den Tipp, zum ersten mal Code gepostet

 

[Fortatus]

Das mit der Formatierung liegt an den falschen Tags. Nutz die Code-Tags anstelle der uote-Tags.

 

[asdfman]

Auf den ersten Blick:
n=n-(n-1) ist das selbe wie n=1
n-1%2==0 ergibt immer beim ersten Mal True, weil n 1 ist, danach immer False, weil n-1 bein n>1 nicht 0 ergibt.
€: subadd(... n++ ...) macht sicher nicht das, was du willst.
€2: Grundsätzlicher Bug: Bufferoverflow, wenn n>100 in main()

 

[ThE_sMoKeY_jOe]

Hehe, stimmt hast recht kann ich einfach n = 1 machen .
Aber bei n-1%2==0 ist es zu beginn doch 0, dann zaehlen wir ja unten durch den erneuten Aufruf der Funktion n++, sollte n-1 dann doch 1 und das nächste mal 2 usw. sein oder ?

 

[asdfman]

1%2 hat Vorrang vor der Subtraktion, also ist der Ausdruck der Selbe wie (n - 1) == 0

 

[Hancock]

n=n-(n-1);

Das ist immer 1, ist das so gewollt?
Was macht dein Programm eig. wenn es funktioniert?

 

[asdfman]

Die Rekursion bricht nie ab, weil beim nächsten Aufruf von subadd n immer noch den Selben Wert hat.
Das sollte der Grund für den Absturz sein.

Entweder rufe subadd mit ++n auf, oder inkrementiere n vorher.

 

[ThE_sMoKeY_jOe]

Hmmm okay das %(mod) Vorrang vor der Subtraktion hat habe ich nicht bedacht aber kann man das nicht mit einer Klammer umgehen, hat das dann nicht Vorrang ?
also wenn ich (n-1)%2==0 mache ? oder muss ich eine neue Variable für den Index des Arrays anlegen ?
Das Problem und wieso ich unten n auf 1 gesetzt habe ist halt das wir von Anfang des Arrays beginnen müssen also bei Index 0.

Also das Programm soll z.B. bei der Eingabe 1, 2, 3, 4

1-2+3-4 rechnen also immer abwechselnd subtrahieren und addieren, ist halt sone Prüfungsaufgabe.

Okay das ++n funktioniert, muss allerdings noch durchsteigen, irgendwie versteh ich es immer noch nicht wieso.

Danke für die Hilfe

 

[Darlis]

n++: nach der aktuellen Anweisung inkrementieren.
++n: vor der aktuellen Anweisung inkrementieren.

Mit ersterem würdest du also mit n in die Rekursion gehen. Erst danach wird n = n+1.
Mit letzterem geht du mit n+1 in die Rekursion, da n noch vor dem Aufruf inkrementiert wurde.

 

[ThE_sMoKeY_jOe]

Danke für die Erklärung, habs mir gerade nochmal angeschaut, also Post und Präinkrement.
Versteh es jetzt auch, freut mich das ich immer wieder das lerne allerdings läuft das Programm noch nicht richtig.

Habe das n =1 jetzt gegen n=0 getauscht, so das ich n-1%2==0 weglassen kann und es eben direkt bei Index 0 beginnt.

Es sieht alles richtig aus wenn ich es durchgehe allerdings gibt es mir einen riesen Wert aus, ich gebe 1 2 3 4 als Zahlen ein und bekomme 163xxxxxxx als Ergebnis.

Ich suche immer ewig nach solchen Fehler, das ist seit heute mittag 14 Uhr erst meine 3 Aufgabe .

Vielleicht könntest Ihr ja nochmal einen Blick drüber werfen ?

include<stdio.h>

int subadd(int zahlen[], int n, int erg, int i)
{
  while(n<=i)
  {
      if(n%2==0)
      {
        erg=erg+zahlen[n];
      }
      else
      {
        erg=erg-zahlen[n];
      }
        subadd(zahlen, ++n, erg, i);
  }
  return erg;
}

int main(void)
{
  int zahlen[100], ergebnis=0, i, n;

  printf("\nAnzahl der Zahlen:");
  scanf("%d", &n);
  printf("\nBitte die Zahlen mit Leerzeichen getrennt eingeben:");
  for(i=0; i<n; i++)
  {
    scanf("%d", &zahlen[i]);
  }
  n=0;
  printf("\nDas Ergebnis ist:%d", subadd(zahlen, n, ergebnis, i));


}

Vielen vielen Dank

 

[Darlis]

Ersetze erst mal while durch if und dann versuche noch das Ergebnis des rekursiven Aufrufs in Zeile 15 zu verwenden.

 

[ThE_sMoKeY_jOe]

Danke für die Hilfe aber ich blick echt nicht durch sorry, grübel schon die ganze Zeit was --->

Ergebnis des rekursiven Aufrufs in Zeile 15 zu verwenden.

Heißen soll, hatte erg=subadd(.........) versucht aber kann wohl nicht gemeint sein .

Versuch mir wirklich mühe zu geben, will ja was lernen aber ich komm einfach nicht drauf.

 

[powerfx]

subadd ist irgendwie doppelt rekursiv. Du führst für jedes n die Fallunterscheidung durch und rufst dann nochmal die Funktion damit auf.

So sollte es funktionieren, ich weiß aber nicht, wie die Aufgabenstellung ist. Vielleicht wird sie nicht erfüllt:

#include<stdio.h>

int subadd(int zahlen[], int n, int erg, int i)
{
    while(n<i)
    {
        if(n%2==0)
        {
            erg=erg+zahlen[n];
        }
        else
        {
            erg=erg-zahlen[n];
        }
        n++;
    }
    return erg;
}

int main(void)
{
    int zahlen[100], ergebnis=0, i, n;

    printf("\nAnzahl der Zahlen:");
    scanf("%d", &n);
    printf("\nBitte die Zahlen mit Leerzeichen getrennt eingeben:");
    for(i=0; i<n; i++)
    {
        scanf("%d", &zahlen[i]);
    }
    n=0;
    printf("\nDas Ergebnis ist:%d", subadd(zahlen, n, ergebnis, i));

    return 0;
}

 

[ph1lipp]

Ja, doch genau das ist damit gemeint.
Lies dir das hier mal durch.

Rekursion macht hier nur nicht wirklich Sinn.
Du könntest in jedem rekursivem Aufruf erg um die letzte Zahl im Array erhöhren/erniedrigen, ob die Zahl eine gerade oder ungerade ist, kannst du über die Größe des Arrays erfahren. Danach musst du ein neues Array erzeugen, dass genau um die schon benutzte letzte Zahl kürzer ist, dieses ergibst du dann rekursiv an sich selbst. Bis dann das Array leer ist und die Rekursion beendet wird. Schau dir das Beispiel im Wikipedia Artikel an.

 

[ThE_sMoKeY_jOe]

@powerfx :

Das liegt, falls ich es richtig verstehen sollte nur am "while" oder nicht ?
Wenn ich mich nicht Irre ist es so wie von dir gepostet nicht mehr rekursiv, da es sich ja nicht selbst aufruft, sondern nur die while Schleife durchgeht und dann return erg; macht.
Sollte funktionieren aber entspricht nicht der Aufgabenstellung.
Wie Darlis schon meinte, das while durch ein if ersetzen, dann passt es besser.

Damit das eigentlich Ziel mal etwas klarer wird :

Es soll eine Funktion subadd(a1,…,an) für n>=1 und ai E N realisiert werden, die
das Ergebnis der Rechnung liefert, bei der von a1 die folgenden Elemente abwechselnd
subtrahiert bzw. addiert werden, also a1-a2+a3-a4+a5… (z.B. subadd(2,7,3,5) ist
-7).
a) Formulieren Sie eine rekursive Definition für diese Funktion. Schreiben Sie die
rekursive Auswertung von subadd(1,2,3,4,5) auf. (5 Punkte)
b) Schreiben Sie die Funktion als rekursive Funktionsdefinition in C auf (korrektes
Einrücken und Bezeichner aus der Aufgabenstellung). (5 Punkte)

Daran sieht man dann auch....
ob es Sinn macht oder nicht habe ich keinen Einfluss drauf, ist halt die Aufgabe .
Ich denke die Rekursion habe ich schon verstanden, 3 von 4 solcher Aufgaben haben heute geklappt nur bei der hapert es, fehlt eben etwas die Übung.
Hatte dieses erg=subadd(....) ausprobiert, leider auch ohne Erfolg, deswegen dachte ich, ich hätte es falsch verstanden.



EDIT:// Okay momentan sieht es so aus, ich habe mir mal die Werte ausgeben lassen in der Funktion damit ich sehe was da abläuft.

#include<stdio.h>

int subadd(int zahlen[], int n, int erg, int i)
{
  if(n<=i)
  {
      if(n%2==0)
      {
        erg=erg+zahlen[n];
      }
      else
      {
        erg=erg-zahlen[n];
      }
        erg=subadd(zahlen, ++n, erg, i);
        printf("\n%d", erg);
        printf("\n%d", n);
        printf("\n%d", i);
        printf("\n%d", zahlen[0]);
  }

      return erg;




}

int main(void)
{
  int zahlen[100], i, n;

  printf("\nAnzahl der Zahlen:");
  scanf("%d", &n);
  printf("\nBitte die Zahlen mit Leerzeichen getrennt eingeben:");
  for(i=0; i<n; i++)
  {
    scanf("%d", &zahlen[i]);
  }
  printf("\nDas Ergebnis ist:%d", subadd(zahlen, 0, 0, i));


}

Aber irgendwie stimmen die Werte nicht....

n bewegt sicht in einem Bereich von 1-4 obwohl ich 0 übergebe, sollte also von 0 starten und durch ++n nur eins mehr sein wie i oder ?

mit i auch, müsste doch bei einer Eingabe von 3 eigentlich 2 sein oder ?
1 zahl ----> i ist 0
2 zahl ----> i ist 1
3 zahl ----> i ist 2

durch die for-Schleife in der i<n steht ( n zu dem Zeitpunkt = 3 ) sollte ja dann fertig sein.

Dadurch ist es kein Wunder wenn man so ein blödes Ergebnis bekommt, i steht ja für den Index des Arrays und bei Index 3 ist ja kein Wert vorhanden.....hmmmm....


Ignoriert das falls ich komplett falsch liegen sollte...


EDIT://

Es läuft jetzt, lag wirklich an dem i, das ein zu hoch war.
Nach etwas rumprobieren habe ich jetzt vor Zeile 40 noch ein "i=n-1;" gesetzt.
Vielleicht kann mir noch jemand von euch erklären wieso das i einen zu hohen Wert hat ?
Ich versteh es nicht.

Danke

 

[maxwell-cs]

auf diesem wege mag man es zwar lösen können, doch würde ich mal sagen, dass der kanonische weg, diese funktion rekursiv zu implementieren, so aussieht:

die funktion bekommt als parameter einen array (also einen int* / int[]) und die länge des arrays (sonst nichts).
intern wird dann einfach die funktion für denselben array und länge-1 aufgerufen, der letzte wert abgezogen oder addiert und das ganze zurückgegeben.

ist deutlich intuitiver als deine version.

edit: nach der for-schleife ist i = n, was genau ist deine frage?

 

[ThE_sMoKeY_jOe]

Das meine Lösung wohl eher schlecht ist denke ich mir .
Da ich aber noch nicht lange Programmiere fehlt mir die Routine und das richtige denken.
Für die Prüfung müssen unsere Algorithmen nicht effizient, sondern nur korrekt sein, daher versuche ich das erste umzusetzen was mir in den Sinn kommt.

Und das mit dem i hat sich jetzt auch erledigt, habe mir gestern erst durch den Thread hier nochmal post und präinkrement angeschaut bzw. wurde mir ja auch noch hier erklärt aber wieder nicht daran gedacht, dass obwohl i<n durch das i++ nochmal eins draufkommt.
Damit wäre wohl alles geklärt.
Nochmals vielen Dank für die gute und schnelle Hilfe, hab einiges dazugelernt.

 

[maxwell-cs]

dass nach der schleife i = n ist, liegt nicht am postkrement, mit ++i wäre es genauso.

der unterschied zwischen ++i und i++ ist nur der wert, den dieser ausdruck zurückgibt.

beide erhöhen i um eins.

++i gibt jedoch i zurück (also den alten wert), i+1, also den neuen wert.

an einer stelle, an der der zurückgegebene wert gar nicht verwendet wird (also z.b. in deiner for-schleife), sind die beiden äquivalent.

dass nach der schleife i=n gilt, liegt an der funktionsweise von for-schleifen:

for(init; bedingung; aktion_nach_iteration) {
   body;
}

diese schleife würde intern in pseudocode so aussehen:

1. init
2. IF bedingung = true GOTO 3. ELSE GOTO 6.
3. body
4. aktion_nach_iteration
5. GOTO 2.
6. END

es wird also erst aufgehört, wenn die bedingung nicht mehr erfüllt ist, in deinem fall: i ist nicht mehr kleiner als n.

übrigens noch eine kleine bemerkung zu i++/++i: ++i ist effizienter als i++, da für i++ eine kopie von i angelegt werden muss, die nach dem erhöhen von i zurückgegeben wird. wenn man die wahl hat, sollte man also ++i statt i++ verwenden, insbesondere dann, wenn der zurückgegebene wert gar nicht verwendet wird (wie typischerweise in for-schleifen).

 

[ThE_sMoKeY_jOe]

Oh man, vielen vielen Dank.
Echt super von Dir mich noch zu korrigieren sonst hätte ich das jetzt die ganze Zeit falsch verstanden.

Habs jetzt aber hoffentlich.

das i=n Problem liegt dann daran, dass nach dem abarbeiten der for Schleife bzw. des bodys nochmal i++ gemacht wird, dann erst wird geschaut ob i<n, trifft nicht zu also wird die Schleife verlassen, i ist ja allerdings schon i=n, so müsste es jetzt stimmen oder ?

Und das mit dem ++i und i++ hab ich auch gerade nochmal genauer angeschaut und habs hoffentlich auch kapiert.

int i=0;

x = ++i; ( x dann 1 und i ebenfalls 1 )
x = i++; ( x noch 0 und i 1 )

Bin da als echt etwas schwer von Begriff, war vielleicht auch etwas zuviel die letzten Tage


Vielen Dank nochmal.

 

[maxwell-cs]

joar, passt soweit - sofern die beiden x= terme alternativ gemeint sind, ansonsten sind natürlich beide werte beim zweiten eins höher

edit: jetzt, wo du ne funktionierende version hast, hab ich dir mal die funktion implementiert, so wie ich es gemacht hätte.

die erste ist schön gut lesbar, man kann aber auch die gesamte funktion in eine zeile quetschen, wenn man denn will (was man natürlich nicht tun sollte, da das nicht mehr lesbar ist).

int subadd(int* data, int size) {
   if (size == 0) {
      return 0;
   }
   else {
      int result = subadd(data, size - 1);
      if (size % 2) {
         result += data[size - 1];
      }
      else {
         result -= data[size - 1];
      }
      return result;
   }
}

oder auch kürzer:

int subadd(int* data, int size) {
   return (size != 0) ? subadd(data, size - 1) + ((size % 2) == 1 ? data[size - 1] : -data[size - 1]) : 0;
}