Analyse der Größe der erzeugten Ausgabe:
Sei die Anzahl der generierten Verlegebefehle für
Scheiben, d.h. bei Aufruf von
Da für zwei neue Aufrufe mit verkleinertem
sowie eine Druckzeile entstehen, gilt offenbar:
d.h., die Wertetabelle beginnt wie folgt:
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Verdacht:
Beweis durch Induktion
Induktionsverankerung:
Induktionsschritt: Sei bis bewiesen:
![]() |
=
![]() |
=
![]() ![]() ![]() |
![]() |
![]() |
|
Rekursionsgleichung | Induktionsannahme |