Geek asks and answers

Haskell: efficiently calculating recursively-defined function values

I want to compute recursively defined function values r(i,j)that are defined

r i j  | i<0 || j<0   = 0
       | i==0 && j==0 = 1
       | otherwise    = (i-1) * r (i-2) j + r (i-1) (j-1)

Obviously, a table of NxNthese coefficients can be calculated in O(N^2). Unfortunately, a simple estimate, for example

[[r i j | j <-[0..50]]| i <- [0..50]]

performed in a critically inefficient way (exponential complexity). Apparently, Haskell builds the entire recursion tree for each r i jand ignores the values ​​previously calculated r (i-1) (j-1), etc.

What is an elegant and efficient way to calculate such a table?

+3
source share
1 answer

As FUZxxl says, this is a question of memoisation.

r i j | i < 0 || j < 0 = 0
      | otherwise      = rss !! i !! j

rss = [[r' i j | j <- [0..]] | i <- [0..]]
  where r' 0 0 = 1
        r' i j = (i-1) * r (i-2) j + r (i-1) (j-1)

50, take 51 (map (take 51) rss) [[r i j | j <-[0..50]]| i <- [0..50]], . r rss .

+3

More articles:


All Articles