我正在读Simon Thompson的 功能编程工艺 在描述递归时，他还提到了一种叫做递归的形式 原始递归。
你能解释一下这种类型的递归与“普通”递归函数有什么不同吗？
这是一个原始递归函数的例子（在Haskell中）：
power2 n
| n == 0 = 1
| n > 0 = 2 * power2(n - 1)
我正在读Simon Thompson的 功能编程工艺 在描述递归时，他还提到了一种叫做递归的形式 原始递归。
你能解释一下这种类型的递归与“普通”递归函数有什么不同吗？
这是一个原始递归函数的例子（在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
原始递归函数的组合也是原始递归的。
另一个例子是Fibonacci数字：
fib Zero = Zero
fib (Succ Zero) = (Succ Zero)
fib (Succ n@(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）。
请注意，仅仅因为函数不是原始递归并不意味着它不会终止;阿克曼的功能是典型的例子。
简化的答案是原始递归函数是根据其他原始递归函数定义的函数，以及自然数结构的递归。自然数在概念上是这样的：
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
原始递归函数的组合也是原始递归的。
另一个例子是Fibonacci数字：
fib Zero = Zero
fib (Succ Zero) = (Succ Zero)
fib (Succ n@(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）。
请注意，仅仅因为函数不是原始递归并不意味着它不会终止;阿克曼的功能是典型的例子。
只能通过do循环实现的递归函数是Primitive递归函数。