提高斯特林数计算效率

Question

我一直在尝试探索Haskell中递归的可能性，但是在面对大递归时如何提高效率我不太了解。今天，我想做一个计算第二类斯特林数的函数：

factorial :: Integer -> Integer
factorial n = helper n 1
    where
        helper 1 a = a
        helper n a = helper (n-1) (a*n)


stirling :: Integer -> Integer -> Integer
stirling n 1 = 1
stirling n 2 = ((2 ^n)- 2) `div` 2
stirling n k
    | k > n      = 0
    | k == n     = 1
    | k == (n-1) = (factorial n) `div` (factorial 2 * (factorial(n-2)))
    | otherwise  = stirling (n-1) (k-1) + k *(stirling (n-1) k)

我一直在尝试创建一个辅助函数，就像阶乘定义中那样，可以避免 Haskell 的惰性求值占用过多内存资源带来的不便。我想做同样的事情，在每次调用中计算乘积

k *(stirling (n-1) k)

递归，但我没有掌握它的窍门。有什么想法吗？

P.D：代码已经运行得相当不错，但我是 Haskell 的新手，我仍然不知道可能性是什么。欢迎任何改进（尽管我认为不使用任何库；我想在进入之前学习基础知识）。

Answer 1

我现在无法写出非常详细的解释，但你可以通过以下方式使其更快一点：

• 使用数学简化一些公式
• 使用移位代替除法
• 使用

  Int

  作为输入而不是

  Integer

然后你会得到这个：

import Data.Bits

stirling :: Int -> Int -> Integer
stirling n 1 = 1
stirling n 2 = (1 `unsafeShiftL` (n - 1)) - 1
stirling n k
    | k > n        = 0
    | k == n       = 1
    | k == (n - 1) = fromIntegral ((n * (n - 1)) `unsafeShiftR` 1)
    | otherwise    = stirling (n - 1) (k - 1) + fromIntegral k * stirling (n - 1) k

我要尝试的下一件事是使用 accumulator style 使非尾递归调用之一成为尾递归，就像在这篇博文中所做的那样：https://www.haskell.org/ghc/blog/20190728 -free-variable-traversals.html