Rekursion

Hast du jemals einen Satz russischer Puppen gesehen? Zuerst siehst Du nur eine Figur, meist aus gemaltem Holz, die vielleicht so aussieht:

Du kannst die obere Hälfte der Puppe entfernen und was siehst du darin? Eine weitere, etwas kleinere, russische Puppe!

Du kannst diese Puppe herausnehmen und ihre Ober- und Unterhälften trennen: Du findest eine weitere, noch kleinere, Puppe:

Und noch einmal:

Und so weiter und so fort. Irgendwann findet man die kleinste russische Puppe. Sie besteht nur aus einem Stück, und kann nicht geöffnet werden:

Wir begannen mit einer großen russischen Puppe, und wir fanden kleinere und kleinere russische Puppen, bis wir auf eine trafen, die so klein war, dass sie keine weiteren Puppen enthalten konnte.

Was haben russische Puppen mit Algorithmen zu tun? So wie eine russische Puppe eine kleinere russische Puppe enthält, die eine noch kleinere russische Puppe in sich hat, bis hin zur kleinsten russischen Puppe, die zu klein ist, um eine andere Puppe zu enthalten, kann man einen Algorithmus entwerfen, der ein Problem löst, indem er eine kleinere Instanz des gleichen Problems lösen, es sei denn, das Problem ist so klein, dass es direkt gelöst werden kann. Wir nennen diese Technik Rekursion.

Rekursion hat eine Vielzahl von Anwendungen. In diesem Modul werden wir lernen, wie man Rekursion benutzt, um die Fakulät einer Zahl zu berechnen, um festzustellen, ob ein Wort ein Palindrom ist, um eine Potenzen von Zahlen zu berechnen, eine Art Fraktal zu zeichnen und das altehrwürdige Türme von Hanoi-Problem zu lösen. Spätere Module verwenden Rekursion, um andere Probleme zu lösen, einschließlich Sortierung.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.