functional-programming - 使用尾递归找到最大值

Question

我正在尝试使用尾递归找到列表的最大值。不过，我不能使用任何辅助功能……所以必须使用递归来完成。我写了一个函数来查找最大值，从头部开始，但不知道如何从尾部开始实现它！

lmax []  = error "empty list"
lmax [x] = x
lmax (x::y::xs) = 
  if x > y then lmax (x::xs)
  else          lmax (y::xs)

Answer 1

术语“尾递归”与列表的尾部无关，它与函数调用的位置有关。

你可以说函数调用处于尾部位置，或者它是尾部调用，如果它是函数中发生的最后一件事，即没有其他计算依赖于它。

相比

fun foo xs = List.length xs

和

fun bar xs = 1 + List.length xs

首先，调用List.length位于尾部位置，因为它的结果会立即返回。
第二，由于我们将长度加 1，所以调用不是尾调用。

“尾递归”是指递归函数调用是尾调用。

所以你很幸运：你的函数已经是尾递归的，因为两个条件分支都只返回递归调用的值。

Answer 2

fun lmax l = let
  fun lmaxh [] a = a
    | lmaxh (x::xs) a = lmax xs Int.max(x,a)
  in
    lmaxh l 0
  end

这可行，假设这些值是非负整数。

Answer 3

实现尾递归优化了效率，因为在创建递归调用后不必评估和“弹出”堆栈。

通常，要使用尾递归，您必须从先前的计算中存储一些“内存”以与当前计算进行比较，并为将来的计算更新它，以便在基本情况下立即退出函数。

因此，您的函数已经是尾递归的。

但是，这里有一个尾递归maxList函数，更符合 SML 的精神：

fun maxList l =
   let 
      fun maxListHelper l acc = 
         case l of 
             [] => acc
           | x :: xs' => if x > acc 
                         then (maxListHelper xs' x) 
                         else (maxListHelper xs' acc)
   in
     case l of
         [] => error "Empty List!"
       | x :: xs' => maxListHelper xs' x
   end

您的函数是用非常类似于 Haskell 的语法编写的，不同的情况在不同的行上处理，而没有在函数定义中显式声明为嵌套情况。这很好，但通常不会在 SML 中完成。