結構性歸納法是一種證明方法，用于數理邏輯（例如，在證明?o?'定理）、計算機科學、圖論和其他一些數學領域。它是對自然數的數學歸納法的概括，并可進一步概括為任意的諾特歸納法。結構性遞歸是一種遞歸方法，它與結構性歸納的關系與普通遞歸與普通數學歸納的關系相同。結構性歸納法被用來證明某個命題P(x)對于某種遞歸定義的結構（如公式、列表或樹）的所有x都成立。在結構上定義了一個有根有據的部分順序（公式的子公式，列表的子列表，樹的子樹）。結構歸納證明是證明該命題對所有最小結構都成立，如果該命題對某一結構S的直接子結構成立，那么它對S也一定成立。(從形式上講，這就滿足了基礎良好的歸納公理的前提，該公理斷言這兩個條件足以使該命題對所有x都成立。)結構遞歸函數使用同樣的思路來定義遞歸函數：基例處理每個最小結構和遞歸規則。結構性遞歸通常通過結構性歸納來證明其正確性；在特別簡單的情況下，歸納步驟往往被省略。下面例子中的length和++函數是結構性遞歸的。例如，如果結構是列表，通常會引入部分排序<，其中只要列表L是列表M的尾部，L就<M。在這種排序下，空列表[]是xxx的最小元素。那么，某個命題P(L)的結構歸納證明由兩部分組成。證明P([])是真的，以及證明如果P(L)對于某個列表L是真的，并且如果L是列表M的尾部，那么P(M)也一定是真的。最終，根據函數或結構的構造方式，可能存在一個以上的基本情況和/或一個以上的歸納情況。在這些情況下，某個命題P(l)的結構歸納證明包括證明P(BC)對每個基例BC都是真的，證明如果P(I)對某個實例I是真的，并且M可以通過應用任何一個遞歸規則一次從I得到，那么P(M)也一定是真的。例子祖先樹是一個眾所周知的數據結構，顯示一個人的父母、祖父母等（見圖片為例）。它是遞歸定義的。在最簡單的情況下，一棵祖先樹只顯示一個人（如果對他們的父母一無所知的話）；或者，一棵祖先樹顯示一個人，以及通過分支連接的他們父母的兩個祖先子樹（為了簡化證明，使用簡化假設，如果其中一個人是已知的，那么兩個人都是）。作為一個例子，通過結構歸納法可以證明以下屬性：一棵延續g代的祖先樹最多顯示2g-1個人。在最簡單的情況下，這棵樹只顯示了一個人，因此也顯示了一代人；對于這樣的樹來說，該屬性是真的，因為1≤21-1。由于后者是整個樹的一個子結構，所以可以假設它滿足要證明的屬性（又稱歸納假設）。也就是說，可以假設p≤2g-1和q≤2h-1，其中g和h分別表示父親和母親的子樹延伸的代數，p和q表示它們顯示的人數。

在g≤h的情況下，整棵樹延伸了1+h代，顯示了p+q+1人，p+q+1≤（2g-1）+（2h-1）+1≤2h+2h-1=21+h-1，即整棵樹滿足21+h-1。在h≤g的情況下，整個樹延伸了1+g代，通過類似的推理，顯示p+q+1≤21+g-1人，即在這種情況下整個樹也滿足該屬性。因此，通過結構歸納，每個祖先樹都滿足該屬性。作為另一個更正式的例子，考慮以下列表的屬性。length(L++M)=lengthL+lengthM[EQ]。這里++表示列表連接操作，而L和M是列表。為了證明這一點，我們需要對長度和連接操作進行定義。讓(h:t)表示一個列表，其頭部（xxx個元素）是h，其尾部（剩余元素的列表）是t，讓[]表示空列表。長度和連接操作的定義是。length[]=0[LEN1]length(h:t)=1+lengtht[LEN2]。[]++list=list[APP1](h:t)++list=h:(t++list)[APP2]我們的命題P(l)是指當L為l時，EQ對所有列表M都是真的。我們想證明P(l)對所有列表l都是真的。首先我們將證明P([])是真的；也就是說，當L恰好是L時，EQ對所有列表M都是真的。