结构递归和结构归纳法的关系就象普通的递归和普通的数学归纳法一样。
结构归纳法 是应用在数学逻辑、计算机科学、图论和一些其他数学领域中的一种证明方法 (比如， Los's 定理的证明). 他是一种特殊化的数学归纳法。
通常， 他用来证明一些命题P(x)， x是一些递归定义的结构（例如树和表）中的一种. 一个良基 偏序 是定义在这种结构上的.结构归纳法的证明是由证明命题对于所有的极小结构成立，以及如果他在一个结构S的基础结构中成立， 那么他一定也在整个S中成立这些组成. 比如， 如果一个结构是个这样一个表，含有偏序 '<'，只要表 L 在表M的尾部，那么L < M. 在这样的排序中，空的list[ ]是唯一的最小元素.结构归纳法中，一些命题P(l) 的证明由两个部分组成：
证明P([])成立
如果P(L) 在表L中成立， 如果L 是表 M的底部， 那么P(M) 也成立。
