原始递归与"正常"递归有何不同？

Question

我目前正在阅读Simon Thompson的The Craft of Functional Programming,在描述递归时,他还提到了一种称为Primitive Recursion的递归形式.

你能解释一下这种类型的递归与"普通"递归函数有什么不同吗？

这是一个原始递归函数的例子(在Haskell中):

power2 n
    | n == 0    = 1
    | n > 0     = 2 * power2(n - 1)

Answer 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 n@(Succ n'  )) = fib n + fib n' -- addition is primitive recursive

Answer 2

原始递归函数是(数学家)对停止问题的自然反应,通过剥夺执行任意无界自递归的能力.

考虑一个"邪恶"的功能

f n
  | n is an odd perfect number = true
  | otherwise = f n+2

f终止了吗？如果不解决是否存在奇数完美数字这一开放性问题,你就无法知道.它能够创建这样的函数,使停顿问题变得困难.

作为构造的原始递归不允许你这样做; 关键是禁止"f n + 2"事物,同时保持尽可能灵活 - 你不能用f(n + 1)来原始递归地定义f(n).

注意,仅仅因为函数不是原始递归并不意味着它不会终止; 阿克曼的功能是典型的例子.