Code optimization of recursive function

Question

I have a mathematical function as shown below

$$ (h+1) * U(k,h) = \sum_{r=0}^k \sum_{s=0}^h (r + 1) * (k - r + 1) * U(r + 1, h - s) * U(k - r + 1, s)\ + \sum_{r=0}^k \sum_{s=0}^h (k - r + 1) * (k - r + 2) * U(r, h - s) * U(k - r + 2, s)\,. $$

Base condition for U(k,h) is

$$ U(k,0) = (-1)^k/k! $$

I am using the following code to calculate the function

public double U(int k, int h)


        {
            h--;
            Int16 r, s;


            if (h == -1)
            {
                return (double)(Power(-1, k) / fact[k]);
            }

            else if (arr1[k, h] != 0 && arr2[k, h] != 0)
                return (double)((arr1[k, h] + arr2[k, h]) / (h + 1));


            else
            {
                for (r = 0; r <= k; r++)
                {
                    for (s = 0; s <= h; s++)
                    {
                        arr1[k,h] += (r + 1) * (k - r + 1) * U(r + 1, h - s) * U(k - r + 1, s);

                    }

                }
                for (r = 0; r <= k; r++)
                {
                    for (s = 0; s <= h; s++)
                    {
                        arr2[k,h] += (k - r + 1) * (k - r + 2) * U(r, h - s) * U(k - r + 2, s);
                    }
                }
                return (double)((arr1[k,h] + arr2[k,h]) / (h + 1));
            }
        }

The function works fine for values of k and h up to 40. After that it prints

at ndp.functions.U(Int32 k, Int32 h)

Answer 1

Base case first

It really helps to get a clear idea of a recursive function when the base case is the first thing you see. In your code it is even worse, as h is mutated before the base case, so it looks like the base case is -1 and not 0.

Smallest scope possible

Declare loop counters inside the for loop statement. It is more efficient and reduces mental load when reading the code.

Answer 2

In a way, this problem is similar to this one, and a possible alternative solution I'd suggest to adopt is similar to the one I suggested in that question. It should become more efficient and more scalable than the current.

Summing it up, I'd suggest to use memoization (used in Dynamic programming methods). The backup data structure I'd suggest is a matrix in which you consider the row index as a value \$r\$ (which has a range of \$[0, k]\$), the column index as a value of \$s\$ (which has a range of \$[0, h]\$), and the cells contain the value of the calculated function for the specific combination of \$r\$ and \$s\$.

The matrix can be populated in a lazy way, you calculate the value in the given position only if it isn't calculated and if you actually need that value. If the value in the given position is already calculated you just use it.

Let me know if anything is unclear.