Strukturinduktion ist eine Probemethode, die in der mathematischen Logik (z.B, im Beweis von Łoś' Lehrsatz), Informatik, Graph-Theorie und einige andere mathematische Felder verwendet wird. Es ist eine Generalisation der mathematischen Induktion. Struktureller recursion ist eine recursion Methode, die dieselbe Beziehung zur Strukturinduktion wie gewöhnliche Recursion-Bären zur gewöhnlichen mathematischen Induktion trägt.

Im Allgemeinen besteht die Idee darin, dass man einen Vorschlag P (x) beweisen möchte, wo x jedes Beispiel einer Art rekursiv definierter Struktur wie Listen oder Bäume ist. Eine wohl begründete teilweise Ordnung wird auf den Strukturen ("Subliste" für Listen und "Subbaum" für Bäume) definiert. Der Strukturinduktionsbeweis ist ein Beweis, dass der Vorschlag für alle minimalen Strukturen hält, und dass, wenn es für die unmittelbaren Unterbauten einer bestimmten Struktur S dann hält, es für S auch halten muss. (Formell das Sprechen, das befriedigt dann die Propositionen eines Axioms der wohl begründeten Induktion, die behauptet, dass diese zwei Bedingungen für den Vorschlag genügend sind, um für alle x. zu halten)

Eine strukturell rekursive Funktion verwendet dieselbe Idee, eine rekursive Funktion zu definieren: "Grundfälle" behandeln jede minimale Struktur und eine Regel für recursion. Struktureller recursion wird gewöhnlich richtig durch die Strukturinduktion bewiesen; in besonders leichten Fällen wird der induktive Schritt häufig ausgelassen. Die Länge und ++ Funktionen im Beispiel ist unten strukturell rekursiv.

Zum Beispiel, wenn die Strukturen Listen sind, führt man gewöhnlich die teilweise Ordnung ein'