Stack für eine Rekursion überwachen

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
elec
Beiträge: 19
Registriert: Di Jul 19, 2022 2:16 pm

Stack für eine Rekursion überwachen

Beitrag von elec » Do Jul 21, 2022 10:10 pm

Aktive Speicherverwaltung ist in C++, so wie ich es bisher verstanden habe, eine Aufgabe des Programmierers.

Eine heutige kurze einführende Erörterung unseres Dozenten, ganz neu ist mir das Thema nicht, von Stack und Heap, hat mich zu einer Frage veranlasst, von der ich befürchte, dass sie in den wenigen noch verbleibenden Kurstagen vielleicht nicht beantwortet wird.

Bekanntlich können rekursive Funktionsaufrufe den verfügbaren Speicher (Stack) überstrapazieren.

Hier, vielleicht eher des reinen Spaßes willen eine Übungsaufgabe, die ich für mich durch Rekursion gelöst habe.

Code: Alles auswählen

#include <iostream>
using namespace std;

unsigned short countCarry( unsigned int eins, unsigned int zwei, 
                           unsigned int carry, unsigned int uebertraege )
{
  // Die letzten Ziffern beider Zahlen ermitteln:
  unsigned int n1 = eins % 10;
  unsigned int n2 = zwei % 10;
  
  // Beide Ziffern und einen eventuell bestehenden Uebertrag addieren und 
  // dabei feststellen, ob es einen Uebertrag gibt und wie gross er ist:
  unsigned sum = n1 + n2 + carry;

  if ( sum > 9 )  // Gegebenenfalls den Uebertragszaehler um eins erhoehen:
  {
    uebertraege += 1;
    carry = sum / 10;
  }

  /*
  cout << "n1 = " << n1 << " / n2 = " << n2 << " / sum = " << sum << endl;
  cout << "new eins: " << eins / 10 << " / new zwei: " << zwei / 10;
  cout << " / carry: " << carry << " / uebertraege: " << uebertraege << endl;
  cout << endl;
  */

  if (eins / 10 > 0 || zwei / 10 > 0 || sum > 10)
  {
    // Die Ausgangszahlen durch 10 geteilt als neue Ausgangszahlen benutzten.
    uebertraege = countCarry( eins / 10, zwei / 10, carry, uebertraege ); 
  }

  return uebertraege;
}

int main()
{
  unsigned short number1 = 0;
  unsigned short number2 = 0;

  cout << "Bitte geben Sie zwei ganze Zahlen grösser als 0 ein!" << endl;
  cout << "Die 1. Zahl: ";
  cin >> number1;
  cout << "Die 2. Zahl: ";
  cin >> number2;

  cout << endl << number1 << " + " << number2 << " = " << number1 + number2 << endl;
  cout << "Bei der Addition ergeben sich " << countCarry(number1, number2, 0, 0) << 
          " Überträge." << endl;
}

/* AUFGABE 9: **********************************************************************
 *
 * Schreiben Sie ein C++-Programm, das die Anzahl der Uebertraege beim Addieren 
 * zweier Zahlen berechnet. 
 *
 * Algorithmus: 
 *
 * Zunaechst sollen vom Benutzer zwei nicht negative Zahlen mit jeweils weniger als 
 * 10 Ziffern eingelesen werden. 
 *
 * Anschliessend soll die Anzahl an Uebertraegen beim ziffernweisen Addieren der 
 * beiden Zahlen von rechts nach links berechnet werden. 
 *
 * Zum Schluss soll die Anzahl an Uebertraegen auf den Bildschirm ausgegeben werden.
 *
 ***********************************************************************************/ 
Diese Aufgabe wird vermutlich kaum je den Stack überfordern, aber Programmieren soll ja möglichst kein Handeln aufgrund von optimistischen Erwartungen sein.

Ich frage mich daher, wie C++-Programmierer abfragen, ob ein Rekursionsschritt den Stack überfordern wird oder wie sie eine solche Problemsituation zumindest geregelt handhaben?

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Stack für eine Rekursion überwachen

Beitrag von Xin » Fr Jul 22, 2022 10:38 am

elec hat geschrieben:
Do Jul 21, 2022 10:10 pm
Aktive Speicherverwaltung ist in C++, so wie ich es bisher verstanden habe, eine Aufgabe des Programmierers.
Ich will den C++-Kurs hier eigentlich überarbeiten, um genau das möglichst weit nach Hinten zu verlegen, denn eigentlich das Aufgabe des C-Programmierers.
Der C++-Programmierer sollte eigentlich RAII nutzen, also Objekte möglichst auf dem Stack anlegen, bzw. diesen Objekten die Speicherverwaltung überlassen.
elec hat geschrieben:
Do Jul 21, 2022 10:10 pm
Eine heutige kurze einführende Erörterung unseres Dozenten, ganz neu ist mir das Thema nicht, von Stack und Heap, hat mich zu einer Frage veranlasst, von der ich befürchte, dass sie in den wenigen noch verbleibenden Kurstagen vielleicht nicht beantwortet wird.

Bekanntlich können rekursive Funktionsaufrufe den verfügbaren Speicher (Stack) überstrapazieren.
Yes, können. Auf dem Amiga war der Default Stack 4096 Bytes groß. Dieser Computer hatte zwischen 256kB und 32MB Speicher und keinen Speicherschutz, weil eine MMU (Memory Management Unit) ein externer Koprozessor war, den man dazu kaufen musste, der aber nicht notwendig war, um den Computer ans Laufen zu bringen. Also sparte man sich das in der Regel.
Das war so zwischen 1985 und 1995.
Moderne Computer haben die MMU in der CPU verbaut. Moderne Betriebsysteme haben Speicherschutz.
Die erste Grenze, die beim Stack auftritt sind 2GB bei 32 Bit Windows.

Du hast also mehr Stack, als die Computer an Speicher, aus der diese Regel stammt. Objekte der Größe von 4096kB würde ich heute ohne auch nur drüber nachzudenken auf den Stack legen, weil es sich nicht lohnt für sowas kleines Speicher zu alloziieren.
elec hat geschrieben:
Do Jul 21, 2022 10:10 pm
Hier, vielleicht eher des reinen Spaßes willen eine Übungsaufgabe, die ich für mich durch Rekursion gelöst habe.
Diese Aufgabe wird vermutlich kaum je den Stack überfordern, aber Programmieren soll ja möglichst kein Handeln aufgrund von optimistischen Erwartungen sein.
In dem Fall darfst Du selbst auf einem Amige davon ausgehen, dass Du den Stack nicht überforderst. :D
elec hat geschrieben:
Do Jul 21, 2022 10:10 pm
Ich frage mich daher, wie C++-Programmierer abfragen, ob ein Rekursionsschritt den Stack überfordern wird oder wie sie eine solche Problemsituation zumindest geregelt handhaben?
Tatsächlich würde ich hier fast schon von einem Freibrief ausgehen. Auf einer 64Bit CPU, die heutzutage eigentlich als Voraussetzung gelten darf, ist die Begrenzung des Stacks die Größe des System-Laufwerks. Und wenn's nicht mehr auf die Festplatten des Systems passt, ist dieser Computer auch nicht in der Lage, das Problem zu lösen. Sollte er also dann abstürzen, ist es halt so. Dann muss man sich wirklich mit der Frage beschäftigen, aber vorher... Feuer frei! ;-)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten