Meine erste Erkenntnis über das «Programmieren» hatte ich als Kind, als ich zu Hause kochen wollte. Ein Rezept ist schliesslich nichts anderes als ein Algorithmus mit Aktionen, die nacheinander ausgeführt werden müssen. Später in der Schule wurden die Rezepte weniger linear. Zum Beispiel hatten wir in Pflanzenkunde ein Buch namens «Le petit botaniste romand». Man konnte damit Pflanzen identifizieren, indem man auf jeder Seite Entscheidungen traf, um auf andere Seiten zu gelangen.
«Teile und herrsche»
Es gibt noch eine andere, mächtige Klasse von Algorithmen, die man «rekursive Algorithmen» nennt. Ihnen begegnen wir im normalen Leben nicht. Ausser, wir lernen, einen Computer zu programmieren. Diese Art von Rezepten funktioniert so, dass eine schwierige Frage in immer kleinere Teile aufgeteilt wird, bis die Lösung fast trivial wird. Fügt man die kleinen Teile zusammen, erhält man die Lösung auf die ursprüngliche Frage.
Diese Vorgehensweise ist dem lateinischen Motto «Divide et impera» (zu Deutsch: «Teile und herrsche») sehr ähnlich, das manchmal Julius Cäsar zugeschrieben wird. Darin spiegelt sich die traditionelle Überzeugung: Politische Macht lässt sich besser ausüben, wenn man die Untertanen in kleine Gruppen aufteilt.
Ganz friedlich
«Rekursive Algorithmen» machen dasselbe ganz friedlich für alltägliche Probleme. Ein Beispiel: Sie stehen am Postschalter in der Schlange. Jemand hinter Ihnen fragt, wie viele Personen in der Schlange warten. Dabei könnten Sie nach folgendem Rezept antworten: Wenn Sie die erste Person vorne in der Schlange sind, lautet die Antwort: «Eine.» Wenn Sie nicht die erste Person sind, fragen Sie die Person, die vor Ihnen steht, und zählen zu deren Antwort eins dazu.
Wenn sich alle an diese zwei Regeln halten, wird die Frage bis zum Anfang der Schlange wandern. Die Antwort wird zum Ende der Schlange gelangen, woraufhin die Gesamtlänge feststeht. Dabei ist egal, wie lang die Schlange ist! Es muss jede Einzelperson in der Schlange nur ein bisschen rechnen, und die schwierige Rechenarbeit, alle Personen in der Schlange zu zählen, wird unter allen verteilt.
Daten sparen
Was hat das mit der digitalen Revolution zu tun? Digitale Bilder auf Smartphones brauchen effiziente Komprimierungsmethoden. Die Effizienz kommt von der Kraft der Rekursion, da praktisch jede Bildkompression im Grunde eine leistungsstarke mathematische Manipulation ist, die man «Fourier-Transformation» nennt. Die Berechnung kostete früher einmal viel Rechenleistung, bis in den 1960er-Jahren ein rekursiver Algorithmus namens «Schnelle Fourier-Transformation» (engl. kurz «FFT») entdeckt wurde.
Die Effizienz dieses neuen Rezepts ist vielleicht die wichtigste Zutat für die sogenannte digitale Revolution. Zum Beispiel würde die Berechnung der Fourier-Transformation für ein Foto mit einem Megapixel aus eintausend Milliarden Rechenoperationen bestehen. Mit der FFT wird dasselbe Ergebnis nach nur 20 Millionen Schritten erreicht! Nicht einmal Cäsar hätte so einen taktischen Erfolg erwarten können. Die FFT ist auf jedem Smartphone vorhanden und gehört zu den wichtigsten Algorithmen des 20. Jahrhunderts.