将递归函数转换为尾递归函数。尾递归的概念

Question

我试图在haskell中转换一些递归函数。为了获得这种函数的一些经验，我试图理解尾递归的概念。为了得到线索，我想从非常简单的函数开始，以理解尾递归背后的概念。以下代码显示了我编写的随机递归函数。我想将它转换为尾递归变体，但我在实际代码中使用理论概念时遇到问题。

h x = if x > 20 then 50 else x*x + h (x+1)

Answer 1

正如Robin Zigmond所说，尾递归的概念在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代码时是道德的：在尝试之前，您不一定知道它很重要，通常依赖于库函数的最抽象的解决方案表现良好。