recursion - 原始递归与 "normal"递归有何不同？

Question

我目前正在阅读西蒙·汤普森的 The Craft of Functional Programming并且在描述递归时，他还提到了一种称为原始递归的递归形式。

你能解释一下这种类型的递归与“普通”递归函数的区别吗？

这是原始递归函数的示例(在 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