Das Prinzip der Rekursion ist äußerst mächtig, wird aber von Anfängern nicht gerne verwendet, weil:

• es oft an ungeeigneten Beispielen erklärt wird, bei denen sein Nutzen nicht einsichtig ist; manche Probleme haben eine einfachere nicht-rekursive Lösung.
• oft auf ungeeignete Weise versucht wird, sich von seiner korrekten Anwendung zu überzeugen; dann kann es recht unübersichtlich werden.

• Wir betrachten die verwendete Teillösung als "black box", von der wir annehmen, daß sie ihren Kontrakt einhält. Ihren Aufbau und ihre interne Funktion betrachten wir auf dieser Stufe nicht! 
• Wir überlegen uns einen Beweis für die Terminierung, also das Abbrechen der rekursiven Zerlegung. Dazu genügt es, ein geeignetes ganzzahliges Größenmaß zu finden und sicherzustellen, daß alle Teilprobleme echt kleiner  sind.
• Wir überlegen uns einen Beweis für die Korrektheit.

Jede nichtleere  Menge von natürlichen Zahlen hat ein kleinstes Element

Wenn unsere Lösung für manche  Problemgrößen fehlerhaft arbeiten sollte, dann gibt es darunter eine kleinste.  Für diese kleinste falsche  Lösung wissen wir aber, daß alle (rekursiv verwendeten) "black boxes" korrekt arbeiten, da sie ja kleiner sind; der Fehler kann also nur an ihrem Zusammenspiel   liegen. Wenn sich das Zusammenspiel der Teilprobleme aber als korrekt herausstellt, so gibt es eine kleinste fehlerhaft arbeitende Instanz gar nicht,  und somit ist unsere Lösung für alle Problemgrößen korrekt!

Dies ist im Grunde ein "auf den Kopf gestellter" Induktionsbeweis nach der Problemgröße, der oft leichter zu finden ist als ein direkter Induktionsbeweis.

Einen solchen Beweis muß man sich für jede rekursive Problemlösung einmal überlegen;  er muß aber nicht sehr formal hingeschrieben werden. Es genügt, sich vom korrekten Zusammenspiel der Teilprobleme zu überzeugen (und darauf zu achten, daß sie echt kleiner sind!), und das gelingt, sofern die Verschachtelung der Teilprobleme nicht zu tief ist, oft durch direktes Hinsehen.