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)

• Jamal: As we all want to make our code more efficient or improve it in one way or another, try to write a title that summarizes what your code does, not what you want to get out of a review.
• πάντα ῥεῖ: @jit thakore at ndp.functions.U(Int32 k, Int32 h) It certainly prints more, if that's an exception message? We provide reviewing working code and suggestions for improvement. If you need debugging help, refer to Stack Overflow please and make sure to show the debugging efforts you've been already doing.
• 200_success: @πάνταῥεῖ If the code is claimed to be working for small inputs, then it's fine for Code Review, because it's a scalability issue.
• πάντα ῥεῖ: @200_success Deleted my answer, though I think breaking up to smaller parts (maybe using indirect recursion) would be a certain improvement.
• Eric Lippert: How is this code even correct? You subtract one from h and then divide by h+1, which means you are dividing by the original h, not by h + 1 as the mathematical expression requires. Do not mutate your parameters; it makes the code very difficult to reason about.

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.