尾递归与受限递归的区别解析——递归类型判定练习疑问

核心差异 #

尾递归 #

• 递归调用是函数的最后一步操作：调用返回后，当前函数直接把这个结果返回出去，不需要再做乘法、列表构造这类额外计算。
• 编译器可以把尾递归优化成循环，不会因为递归深度太大导致栈溢出。
• 每次递归都会严格缩小问题规模，比如参数n减1、列表去掉首元素，确保递归能终止。

受限递归 #

• 递归的调用次数是有限且固定的，不会随着输入规模变大而线性增长。通常是用来修正输入的某个属性（比如把正元素改成负的），之后才会进入常规的递归处理。
• 递归过程中，问题规模可能暂时没缩小（比如列表长度不变，只是改了个元素），但最多递归几次就会触发能缩小规模的分支。
• 没法被编译器自动优化成循环，因为递归调用后可能还有后续操作，或者递归只是有限次数的修正步骤。

给定函数的类型判定 #

1. pow2 #

pow2 0 = 1
pow2 n = 2 * pow2 (n-1)

线性递归
递归调用pow2 (n-1)之后还得做乘法，不是尾递归；每次递归都把n减1缩小问题规模，但没有受限递归那种有限次数的修正逻辑。

2. factAux（factorial的辅助函数） #

factAux r i n
  | i <= n = factAux (i * r) (i + 1) n | otherwise = r
factorial = factAux 1 1

尾递归
递归调用factAux (i*r) (i+1) n是函数的最后一步，调用完直接返回结果；每次通过i+1推进，最终会触发终止条件返回，完全符合尾递归的特征。

3. init #

init [x] = []
init (x:xs) = x : init xs

线性递归
递归调用init xs之后还要构造新列表x : ...，不是尾递归；每次递归去掉列表首元素缩小规模，不属于受限递归。

4. binom #

binom n 0 = 1
binom n k
  | n == k = 1
  | otherwise = binom (n - 1) k + binom (n - 1) (k - 1)

分治递归
每次递归会生成两个分支，属于分治递归范畴，不在你提到的线性/尾/受限递归分类里。

5. negList #

negList [] = []
negList (x : xs) = if x > 0 then negList (-x : xs) else x : negList xs

受限递归
遇到正的首元素时，会递归调用negList (-x:xs)——这里列表长度没变，但只会递归1次（下一次首元素就是负数，会走else分支）；else分支里的negList xs是线性递归，但整体存在有限次数的输入修正步骤，符合受限递归的定义。

内容的提问来源于stack exchange，提问作者immi0815