为什么这个递归很慢？ [英] Why is this recursion slow?

问题描述

我试图解决这个问题：

I'm trying to solve the problem:

有多少种方式可以使用1c，5c，10c， 25c或50c硬币？

How many ways are there to get $50 using only 1c, 5c, 10c, 25c, or 50c coins?

以下是我的代码：

Here's my code:

main = print $ coinCombinations [1,5,10,25,50] !! 5000

coinCombinations coins = foldr recurse (1 : repeat 0) coins
  where recurse a xs = take a xs ++ zipWith (+) (drop a xs) (recurse a xs)

事实证明，我的递归函数很慢，也许是二次或更糟。但我不明白为什么，因为它看起来类似于斐波纳契列表

It turns out that my recurse function is slow, maybe quadratic time or worse. But I don't understand why, since it looks similar to the fibonacci list

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

推荐答案

递归的问题是需要注意不要成指数地分支或具有指数记忆足迹;并且写一个尾递归函数通常不那么富有表现力。

The problem with recursion is that care needs to be taken not to branch exponentially or have exponential memory foot-print; and also writing a tail recursive function is usually less expressive.

您可以通过动态编程绕过整个递归开销;在Haskell中使用正确的折叠有一个非常高性能的实现：

You can bypass the entire recursion overhead by dynamic programming; which has a very performant implementation in Haskell using a right fold:

count :: (Num a, Foldable t) => t Int -> Int -> a
count coins total = foldr go (1: repeat 0) coins !! total
    where
    go coin acc = out where out = zipWith (+) acc $ replicate coin 0 ++ out

然后：

then:

\> count [1, 5, 10, 25, 50] 5000
432699251

欧拉项目的第31个问题 ^（1）：

\> count [1, 2, 5, 10, 20, 50, 100, 200] 200
73682

less 有效的选择是使用不可变的非严格（盒装）数组：

A less efficient alternative would be to use immutable non-strict (boxed) arrays:

import Data.Array (listArray, (!))

count :: (Num a, Foldable t) => t Int -> Int -> a
count coins total = foldr go init coins ! total
    where
    init = listArray (0, total) $ 1: repeat 0
    go coin arr = out
        where
        out = listArray (0, total) $ map inc [0..total]
        inc i = arr ! i + if i < coin then 0 else out ! (i - coin)

---

_{（1 ）问题已经发布在其他地方的stackoverflow;请参阅在Haskell中使用动态编程？ [警告：ProjectEuler 31解决方案]}

这篇关于为什么这个递归很慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！