原始遞歸模式(primitive recursion schema )遞歸論術語，指定義函式的一種方法。
基本介紹
- 中文名：原始遞歸模式
- 類型：遞歸論術語
給定一個n元函式g和n+2元函式h，由下式可以定義一個n+1元新函式.f
原遞歸式
上式稱為原遞歸式或原始遞歸模式.其中y稱為遞歸變元，x稱為參數.此時，函式f稱由g,h經原始遞歸定義的函式，或稱f是原始遞歸於g,h的.原始遞歸模式定義函式的特點是:直接指定函式在y=o處的值，而對其在y+1處的值則利用一些已知函式及新函式在y處的值來確定.因此，新函式的值可依遞歸變元逐步減小而逐步遞推求得.這正是遞歸一詞的來源.此外，又由於這種遞推的過程是比較簡單的(相對於一般遞歸而言)，因此，特稱為原始遞歸.這個名稱最初是由挪威數學家斯科朗(Skolem,A. T.)於1936年引進的.就定義函式的能力而言，原始遞歸式有許多等價形式，它們都是原始遞歸式的變種(參見“原始復迭式”、“串值遞歸式”、“聯立遞歸式”、“參數變異遞歸式”、“嵌套遞歸式”、“多重遞歸式”等).
