实现尾递归

Question

我在 haskell 中编写了一个简单的函数，它是非尾递归的，它对列表中的值求和，其中：

nonTailRecursiveSum :: [Integer] -> Integer
nonTailRecursiveSum [] = 0 --base case
nonTailRecursiveSum (x:xs) = x + sum xs

但我现在要做的是实现相同的功能，但使用尾递归。据我所知，尾递归在最后一步执行递归调用所以我尝试了类似的东西：

tailRecursiveSum :: [Integer] -> Integer
tailRecursiveSum [] = 0
tailRecursiveSum (x:xs) = aux_f(x) + tailRecursiveSum xs
.
.

但是我在中途迷路了，因为我不熟悉 Haskell 中的尾递归。谁能帮我继续尾递归版本的代码？

Answer 1

玩一下，

sum (x:y:xs) = x + sum (y:xs)
             = x + (y + sum xs)
             = (x + y) + sum xs

g a b = a + sum b

sum (x:y:xs) = g x (y:xs)
             = x + g y xs
             = g (x+y) xs   -- !!!

最后一个是尾递归形式！因此我们只定义

sum xs = g 0 xs
  where
  g acc [] = ...
  g acc (x:xs) = g (acc + ...) ...

填空！

实现尾递归

Implementing tail recursion

haskell

recursion

tail-recursion