Einmal hat er uns einen Algorithmus am Overheadprojektor demonstriert mit Bauklötzchen unterschiedlicher Größe die man nach bestimmten Regeln von einem Platz auf einen anderen schieben mußte, es durfte nie ein größeres über einem kleineren liegen oder so ähnlich.
Ach ja - das andere "Standardproblem". Das sind die berühmten "Türme von Hanoi".
Und was soll damit gezeigt werden? Die sog. "Rekursion". Das ist ein wesentlicher Bestandteil in der Programmierung, die sog. rekursive Programmierung. Und diese "Türme von Hanoi" ist ein klassisches rekursives Problem - man hat einen Turm aus einer Anzahl übereinanderliedener Scheiben und man hat drei Abstellplätze, auf einem steht der fertige Turm (wie eine Pyramide von unten nach oben schlanker werdend, weil die Scheiben immer kleiner werden) und man muss diesen Turm komplett auf ein freies Feld bringen. Dazu darf man jeweils nur eine oberere Scheibe abnehmen und entweder auf einen freien Platz oder auf einen Turm legen, aber man darf nicht eine größere Scheibe auf eine kleinere legen.
Und dieses Problem läßt sich rekursiv (und ähnlich wie vollständige Induktion) so lösen, dass man wie folgt überlegt:
Der hat Turm besteht aus n Scheiben.
a) man legt die kleinste Scheibe von oben auf eines der freien Felder
b) nun hat man einen Turm mit (n-1) Scheiben übrig. Hier beginnt die Überlegung quasi von vorne, die Aufgabe ist die gleiche wie am Anfang, nun muss ich diesen kleineren Turm verschieben, dieser wird nach dieser hier festgelegten Regel auf das andere freie Feld geschoben. Das geht natürlich nicht in einem Rutsch.
Dieser Punkt wird so lange "unterverschachtelt", bis der zu verschiebende Turm nur noch einen Stein besitzt - und den kann man nun einfach umlegen.
c) danach legt man von einem Nachbarfeld den "Restturm" zurück auf den untersten Stein, auch das geschieht wieder als rekursive Unteraktion (gleiches Problem - Turm verschieben). Bis man das so oft unterverschachtelt hat, dass man nur noch einen Stein umlegen muss, den legt man wirklich zurück.
Es ist ein sehr vertrackter Gedankengang, man muss immer daran denken, dass das Problem immer das gleiche ist, weil man "Untertürme" verschiebt.
Und so etwas man kann mit den moderenen Programmiersprachen sehr schön programmieren. Und das heißt "Rekursion", im Kopf kann man das nur sehr schwer auflösen, der Computer macht das natürlich in Windeseile.
Und jetzt Fibonacci, das ist auch ein rekursives Problem, man kann die n-te Position berechnen, in dem man die (n-1) und die (n-2)-te Position berechnet und zusammenzählt. Dazu muss man aber wieder unterverschachteln, um diese beiden Positionen zu berechnen. Und so weiter, irgendwann braucht man die 1. und die 2. Position und dann löst es sich endlich auf, die sind beide gleich 1 und dann wickelt sich Programm "von hinten zurück". Das gilt als Musterbeispiel für eine schlechte Rekursion, denn wenn man das aufmalt, was war für gewaltige Untersysteme aufgemacht werden, da rechnen sich selbst schnelle Rechner schon sehr bald kaputt. Die kommen nie an. Und deswegen wird dieses Beispiel in der Informatik benutzt, um auch die Kehrseite der rekursiven Programmierung zu zeigen. Es wäre viel einfacher, von links nach die Zahlen zusammenzuzählen und eine lange Kette zu bilden.