我正在閱讀Simon Thompson的The Craft of Functional Programming，並且在描述遞歸時，他還提到了一種遞歸形式，稱爲原始遞歸。原始遞歸如何與「正常」遞歸不同？
你能解釋一下這種類型的遞歸與「正常」遞歸函數不同嗎？
這裏的（在Haskell）一個原始遞歸函數的一個例子：
power2 n
| n == 0 = 1
| n > 0 = 2 * power2(n - 1)
一個簡單的答案是，原始遞歸函數是根據其他原始遞歸函數定義的函數，以及自然數結構的遞歸函數。自然數的概念是這樣的：
data Nat
= Zero
| Succ Nat -- Succ is short for 'successor of', i.e. n+1
這意味着你可以在他們遞歸這樣的：
f Zero = ...
f (Succ n) = ...
我們可以寫你的例子爲：原始遞歸函數
power2 Zero = Succ Zero -- (Succ 0) == 1
power2 (Succ n) = 2 * power2 n -- this is allowed because (*) is primitive recursive as well
組成也是原始遞歸。
又如斐波那契數：
fib Zero = Zero
fib (Succ Zero) = (Succ Zero)
fib (Succ [email protected](Succ n' )) = fib n + fib n' -- addition is primitive recursive
原始遞歸功能是停機問題一個（數學家的）的自然反應，通過汽提掉功率做任意無限的自遞歸。
考慮一個 「邪惡」 的功能
f n
| n is an odd perfect number = true
| otherwise = f n+2
是否˚F終止？如果沒有解決是否存在奇數完美數字的公開問題，你是無法知曉的。這是創建類似這樣的功能的能力，這使得停止問題變得困難。
原始遞歸作爲構造不會讓你這樣做;關鍵是要禁止「f n + 2」事物，同時仍然保持靈活 - 你不能以f（n + 1）的形式原始遞歸地定義f（n）。
請注意，只是因爲一個函數不是原始的遞歸併不意味着它不會終止;阿克曼的功能就是典型的例子。
那麼，建立好的遞歸和原始遞歸之間有什麼區別？ – Hibou57 2015-12-29 08:50:14
只能由做來實現的遞歸函數環是原始遞歸函數。
只是FYI（根據你的其他職位，而不是這一個），你可以在http://careers.stackoverflow.com/ – 2010-09-03 11:22:30
上發佈簡歷。循環變量嚴格減少循環。 – ARi 2015-10-02 15:31:08
...非常有幫助-_- – 2009-11-11 00:37:36
你願意我複製粘貼它的某些部分嗎？如果原始遞歸存在一些你不瞭解的方面，可以提供更好的答案，但是「它與一般遞歸有什麼不同」，只能通過查看維基百科中的定義來回答。 – 2009-11-11 00:55:52
OP正試圖在這裏學習一些東西。如果你是數學老師，你會把你的學生引用到百科全書嗎？ – 2009-11-11 01:30:33