时间戳

首页 > 解决方案 > 实现尾递归

haskell - 实现尾递归

问题描述

我在 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 中的尾递归。任何人都可以帮助我继续代码的尾递归版本吗？

标签： haskellrecursiontail-recursion

解决方案

玩了一会儿，

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 + ...) ...

填空！

推荐阅读