如何将这个二进制递归函数转换为尾递归形式？

Question

对于在函数下关闭的集合,有一种明确的方法可以将二进制递归转换为尾递归,即为Fibonacci序列添加整数:

(使用Haskell)

fib :: Int -> Int
fib n = fib' 0 1 n

fib' :: Int -> Int -> Int
fib' x y n
    | n < 1 = y  
    | otherwise = fib' y (x + y) (n - 1)

这工作,因为我们有我们的期望值y,而我们的操作,x + y其中x + y返回一个整数,就像y做.

但是,如果我想使用未在函数下关闭的集合,该怎么办？我想采用一个将列表拆分为两个列表的函数,然后对这两个列表执行相同的操作(例如递归创建二叉树),当另一个函数神奇地说明何时停止查看结果分割时,我停止:

[1, 2, 3, 4, 5] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

那是,

splitList :: [Int] -> [[Int]]
splitList intList
    | length intList < 2    = [intList]
    | magicFunction x y > 0 = splitList x ++ splitList y
    | otherwise             = [intList]
  where
    x = some sublist of intList
    y = the other sublist of intList

现在,如何将这个二进制递归转换为尾递归？先前的方法不会明确地工作,因为(Int + Int -> Int与输入相同)但是(Split [Int] -/> [[Int]]与输入不同).因此,需要更改累加器(我假设).

Answer 1

有一个通用技巧可以使任何函数尾递归:在连续传递样式(CPS)中重写它.CPS背后的基本思想是每个函数都需要一个额外的参数 - 一个在完成后调用的函数.然后,原始函数不是返回值,而是调用传入的函数.后一个函数称为"延续",因为它继续计算到下一步.

为了说明这个想法,我将以你的函数为例.请注意类型签名的更改以及代码的结构:

splitListCPS :: [Int] -> ([[Int]] -> r) -> r
splitListCPS intList cont
  | length intList < 2    = cont [intList]
  | magicFunction x y > 0 = splitListCPS x $ \ r? -> 
                              splitListCPS y $ \ r? -> 
                                cont $ r? ++ r?
  | otherwise             = cont [intList]

然后,您可以将其包装成看起来很正常的函数,如下所示:

splitList :: [Int] -> [[Int]]
splitList intList = splitListCPS intList (\ r -> r)

如果你遵循稍微复杂的逻辑,你会发现这两个函数是等价的.棘手的一点是递归情况.在那里,我们马上打电话splitListCPS给x.该函数\ r? -> ...告诉splitListCPS它在完成时要做什么 - 在这种情况下,splitListCPS使用下一个参数(y)调用.最后,一旦我们得到两个结果,我们只是将结果组合起来并将其传递给原始的continuation(cont).所以最后,我们得到了我们原来的相同结果(即splitList x ++ splitList y),但我们只是使用延续而不是返回它.

此外,如果您查看上面的代码,您会注意到所有递归调用都处于尾部位置.在每一步中,我们的最后一个操作始终是递归调用或使用延续.使用聪明的编译器,这种代码实际上可以非常有效.

从某种意义上说,这种技术实际上与你所做的相似fib; 但是,我们不是维持累加器值,而是维护我们正在进行的计算的累加器.