Wissensspeicher 9

Gültigkeitsbereiche

Bisher: Variablen sind innerhalb eines Blocks sichtbar

Neu: Globale Variablen
- … werden außerhalb der Funktionen deklariert (und bitte initialisiert)
- … sind ab Deklaration im weiteren C++-Code sichtbar

Neu: Namensüberdeckung
- Variablen gleichen Namens innerhalb eines Blocks überdecken äußere Variablen
- Am Ende eines Blocks endet die Sichtbarkeit (und ggf. die Existenz) einer inneren Variablen
- Zugriff auf globale Variablen mit scope resolution operator :: jeder Zeit möglich
- Sorgt nicht selten für Verwirrung → Bitte vermeidet Namensüberdeckungen

Live-Demo - Fakultät

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

long fakultaet(int n) {
    if (n == 0) return 1;         // Rekursionsverankerung
    return n * fakultaet(n - 1);  // Rekursionsschritt
}

int main() {
    int n = 10;
    cout << n << "! = " << fakultaet(n) << endl;
    n = 100000;
    long f;
    time_point<steady_clock> jetzt = steady_clock::now();
    f = fakultaet(n);
    time_point<steady_clock> spaeter = steady_clock::now();
    duration<double> zeit = spaeter - jetzt;

    cout << n << "! = " << f << endl;
    cout << "Zeit rekursiv: " << zeit.count() << " sec." << endl;
	return 0;
}

compiler

Live-Demo - Fakultät rekursiv vs. iterativ

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

long fakultaet(int n) {
	if (n == 0) return 1;         // Rekursionsverankerung
	return n * fakultaet(n - 1);  // Rekursionsschritt
}

long long fakultaetIter(int n) {
	long wert = 1;
	while (n > 0) wert *= n--;
	return wert;
}

int main() {
	int n = 10;
	cout << n << "!=" << fakultaet(n) << endl;

	n = 20;
	cout << n << "!=" << fakultaet(n) << endl;

	n = 100000;
	long f;
	time_point<steady_clock> jetzt = steady_clock::now();
	f = fakultaet(n);
	time_point<steady_clock> spaeter = steady_clock::now();
	duration<double> zeit = spaeter - jetzt;

	cout << f << endl;
	cout << "Zeit rekursiv: " << zeit.count() << " sec." << endl;

	jetzt = steady_clock::now();
	f = fakultaetIter(n);
	spaeter = steady_clock::now();
	zeit = spaeter - jetzt;

	cout << f << endl;
	cout << "Zeit iterativ: " << zeit.count() << " sec." << endl;

    return 0;
}

compiler

Live-Demo - Anzahl rekursiver Aufrufe

#include <iostream>

using namespace std;

// Anzahl rekursiver Aufrufe, wenn die Funktion
// sich genau einmal selber aufruft
int rekursiv1(int n) {
    if (n == 1) return 1;
    int a;
    a = rekursiv1(n - 1);
    return a + 1;
}

// Anzahl rekursiver Aufrufe, wenn die Funktion
// sich genau zweimal selber aufruft
int rekursiv2(int n) {
    if (n == 1) return 1;
    int a, b;
    a = rekursiv2(n - 1);
    b = rekursiv2(n - 1);
    return a + b + 1;
}

// Anzahl rekursiver Aufrufe, wenn die Funktion
// sich genau dreimal selber aufruft
int rekursiv3(int n) {
    if (n == 1) return 1;
    int a, b, c;
    a = rekursiv3(n - 1);
    b = rekursiv3(n - 1);
    c = rekursiv3(n - 1);
    return a + b + c + 1;
}

// Anzahl lokaler Variablen bei 2 rekursiven
// Aufrufen und 3 Parametern
// (die Variablen a und b sind nur für die Berechnung
//  und werden nicht mitgezählt)
int rekursiv23(int n, int li, int re) {
    if (n == 1) return 3;
    int a, b;
    a = rekursiv23(n - 1, li, re);
    b = rekursiv23(n - 1, li, re);
    return a + b + 3;
}

int main() {
    cout << "rekursiv1(10) : " << rekursiv1(10) << endl;
    cout << "rekursiv2(10) : " << rekursiv2(10) << endl;

    cout << "------" << endl;
    for (int i = 1; i <= 20; ++i) {
        cout << i << " : " << rekursiv2(i) << endl;
    }
    cout << "------" << endl;
    for (int i = 1; i <= 10; ++i) {
        cout << i << " : " << rekursiv3(i) << endl;
    }
    cout << "------" << endl;

    cout << "rekursiv23(10) : " << rekursiv23(10, 1, 1) << endl;
    cout << "rekursiv23(20) : " << rekursiv23(20, 1, 1) << endl;

    return 0;
}

compiler

Warum ist eine große Zahl an rekursiven Aufrufen gefährlich?

// Anzahl rekursiver Aufrufe, wenn die Funktion
// sich genau dreimal selber aufruft
int rekursiv3(int n) {
    if (n == 1) return 1;
    int a, b, c;
    a = rekursiv3(n - 1);
    b = rekursiv3(n - 1);
    c = rekursiv3(n - 1);
    return a + b + c + 1;
}

Pro Aufruf werden drei Variablen auf dem Stack abgelegt
Pro Aufruf werden drei weitere Aufrufe erzeugt
Für große $n$ gibt es dementsprechend viele rekursive Aufrufe

→ Mit jedem Aufruf verdreifacht sich die Anzahl der Variablen auf dem Stack

→ 🚨 Gefahr 🚨 eines Stacküberlaufs