Rekursion und Aufrufstack
Jede rekursive Funktion braucht einen Basisfall und Fortschritt dorthin.
Was ist Rekursion und Aufrufstack?
Jede rekursive Funktion braucht einen Basisfall und Fortschritt dorthin.
Löse ein Problem durch kleinere Instanzen.
Wichtige Punkte
- Teste leere, einzelne, doppelte und sortierte Eingaben.
- Trenne Korrektheit von Optimierung.
- Nutze in Produktivcode bevorzugt die Standardbibliothek.
Codebeispiele in C und C++
main.c
#include <stdio.h>
unsigned long long factorial(unsigned number) {
return number < 2 ? 1 : number * factorial(number - 1);
}
int main(void) {
printf("%llu\n", factorial(6));
}
720main.cpp
#include <iostream>
constexpr unsigned long long factorial(unsigned number) {
return number < 2 ? 1 : number * factorial(number - 1);
}
int main() {
constexpr auto value = factorial(6);
std::cout << value << '\n';
}
720Vergleich zwischen C und C++
Fakultät benötigt O(n) Zeit und O(n) Stack. Große Eingaben erfordern Prüfung und oft eine iterative Lösung.
C
Schleifen, Pointer, Längen und Puffer sind explizit.
C++
Iteratoren und Algorithmen trennen Operation und Speicherung.
Übungsaufgaben
Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.
- Verfolge jeden Vergleich manuell.
- Teste Duplikate und Extremwerte.
- Vergleiche die Laufzeit mit der Standardbibliothek.