将递归函数转换为尾递归函数。尾递归概念
将递归函数转换为尾递归函数。尾递归概念
提问于 2019-04-25 10:22:42
我试图在haskell中转换一些递归函数。为了获得这类函数的经验，我尝试理解尾递归的概念。为了得到一个线索，我想从非常简单的函数开始，来理解尾递归背后的概念。下面的代码显示了我编写的随机递归函数。我想把它转换成尾递归变体，但是我在实际代码的理论概念上有问题。
h x = if x > 20 then 50 else x*x + h (x+1)回答 1
Stack Overflow用户
发布于 2019-04-25 11:03:44
正如Robin所说，尾递归的概念在Haskell并不像在非懒惰语言中那样适用。在具有非惰性语义的语言(所以不是Haskell)中，实现尾递归的方法是将导致堆栈使用的表达式移动到如下所示的累加参数：
h :: Int -> Int
h x = if x > 20 then 50 else x*x + h (x+1)
g :: Int -> Int
g z = g' z 50 where
g' x y
| x > 20 = y
| otherwise = g' (x+1) (x*x + y)在这里，g'函数体的外部表达式是对自身的调用，因此如果这是一种非惰性语言，那么在解析表达式的x*x + ...部分之前，不需要保留旧递归调用的堆栈框架。不过，在Haskell中，评估结果不同。
在微基准测试中比较你的h和这个g，
module Main where
import Criterion
import Criterion.Main
main :: IO ()
main = defaultMain [ bgroup "tail-recursion" [ bench "h" $ nf h 1
, bench "g" $ nf g 1
]
]您实际上从这个g'中得到了更糟糕的性能
benchmarking tail-recursion/h
time 826.7 ns (819.1 ns .. 834.7 ns)
0.993 R² (0.988 R² .. 0.997 R²)
mean 911.1 ns (866.4 ns .. 971.9 ns)
std dev 197.7 ns (149.3 ns .. 241.3 ns)
benchmarking tail-recursion/g
time 1.742 μs (1.730 μs .. 1.752 μs)
1.000 R² (0.999 R² .. 1.000 R²)
mean 1.742 μs (1.729 μs .. 1.758 μs)
std dev 47.44 ns (34.69 ns .. 66.29 ns)您可以通过严格执行g'的参数来恢复某些性能，
{-# LANGUAGE BangPatterns #-}
g2 :: Int -> Int
g2 z = g' z 50 where
g' !x !y
| x > 20 = y
| otherwise = g' (x+1) (x*x + y)但是它看起来和性能都比原来的h差。
benchmarking tail-recursion/g2
time 1.340 μs (1.333 μs .. 1.349 μs)
1.000 R² (0.999 R² .. 1.000 R²)
mean 1.344 μs (1.336 μs .. 1.355 μs)
std dev 33.40 ns (24.71 ns .. 48.94 ns)编辑:正如K.A.Buhr所指出的，我忘记了GHC的-O2标志；这样做提供了以下微基准测试结果：
h time: 54.27 ns (48.05 ns .. 61.24 ns)
g time: 24.50 ns (21.15 ns .. 27.35 ns)
g2 time: 25.47 ns (22.19 ns .. 29.06 ns)此时，累积参数版本确实执行得更好，而BangPatterns版本也只是执行得更好，但两者看起来都比原始版本差。
因此，在一般情况下，尝试优化代码时有一个寓意:不要过早地去做。尤其是在优化Haskell代码时，这是一个寓意:在尝试之前，您不一定知道这很重要，而且通常依赖于库函数的最抽象的解决方案执行得很好。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55847058
复制相关文章
相似问题
腾讯云开发者
