尾递归实现相邻元素最小距离函数的正确性确认及概念咨询

什么是尾递归？ #

尾递归是递归的一种特殊形式：函数执行的最后一个操作就是调用自身，没有任何需要在递归调用返回后再完成的计算步骤。

对比普通递归和尾递归的差异：

• 普通递归：比如计算阶乘的fact n = n * fact (n-1)，递归调用fact(n-1)返回后，还要和n相乘，这一步是递归返回后的额外计算，无法被编译器优化，递归深度过大时容易栈溢出。
• 尾递归：把中间结果通过参数传递（比如累加器acc），递归调用就是函数的最后一步动作，没有后续计算。比如factTail n acc = if n == 0 then acc else factTail (n-1) (n*acc)，编译器可以把这种递归直接转换成循环，避免栈溢出问题。

给出的代码分析 #

首先指出代码的两个核心问题：

1. 拼写错误：定义的函数名为minimumdistance，但后续分支写成了minimaldistance，这会直接导致编译失败。
2. 逻辑错误：helper函数中计算abs(y - z)时，y是外层函数的固定参数，不会随着递归更新。比如输入[1,3,5,2]，正确的相邻差应该是2、2、3，但当前代码会计算2、2、1（一直用最初的y=3和后续元素算差），完全不符合需求。

是否是尾递归？ #

从形式上看，helper函数的递归调用是最后一步操作：无论是helper (abs (y - z)) zs还是helper acc zs，都是函数的最终动作，没有后续计算，符合尾递归的形式。但因为逻辑错误，这个函数根本无法正确完成“计算相邻元素最小距离”的任务。

正确的尾递归实现 #

修正后的代码需要跟踪当前的前一个元素，而非固定使用初始的y，标准的尾递归写法如下：

minimumDistance :: [Int] -> Int
minimumDistance [] = error "Empty list"
minimumDistance [_] = error "Requirement is not met"
minimumDistance (x:y:xs) = helper (abs (x - y)) y xs
  where
    helper :: Int -> Int -> [Int] -> Int
    helper acc _ [] = acc
    helper acc prev (z:zs) =
      let currentDiff = abs (prev - z)
          newAcc = min acc currentDiff
      in helper newAcc z zs

这里的helper函数通过prev参数跟踪前一个元素，每次递归更新prev为当前元素z，同时用newAcc保存当前的最小距离，递归调用是函数的最后一步，是标准的尾递归实现。

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