Converting a function with single parameter to a function with multiple parameters

Question

I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:

Given a string or a list, do an aggregation operation on each of its elements. Here in each of these elements we apply some recurrence to solve it.

An example of one such problem is below.

---

Problem: Given n integers return the total number of binary search trees that can be formed using the n integers

To solve this problem, I define a recurrence relation as follows:

f(n) = 1 // if n = 0
f(n) = ∑ f(i) * f(n-i-1) where 0 <= i <= n-1

This works and I get the correct answer however I want to modify the function a bit.

Instead of expressing the function in terms of f(n) I want to express it in terms of f(n, i) so I can remove the summation. However I am unable to do it correctly.

---

Code

My code to solve the problem by defining the recurrence in terms of f(n) is as follows: (I am aware it can be optimized by DP but that is not what I am trying to do here)

public int f(int n) {
    if(n == 0)
        return 1;

    int result = 0;
    for(int i = 0; i< n; i++)
        result += f(i) * f(n-i-1);
    return result;
}

I want to remove that for loop and instead express the function in terms of f(n,i) instead of f(n).

---

Question

1. How to convert the recurrence shown above from f(n) to f(n,i) and remove the summation?
   • Here 'n' is the size of the list of element and 'i' is the ith element in the list that we choose to be the root of the tree.

Answer 1

You could do it by making the second parameter of your function function like the index of the summation, and recursively increment this parameter as long as $0 \leq i < n$.

$$f(n, i) = \begin{cases} 1 & \text{if } n =0\\ f(i, 0)\cdot f(n-i-1,0) + f(n, i+1) & \text{if } 0 \leq i < n\\ 0 & \text{otherwise}\\ \end{cases}$$

Then $f(n, 0)$ gives you the answer you want.