I am trying to convert a recursion into a mathematical formula. The code snippet (c++) below is a simplified variant. The values look like an exponential function, however I am trying to find a closed form. For example, rec(8, 6)
is 1287. As an assumption, I first assumed 6 to be constant and tried to find an exponential function for rec(?, 6)
. However, these results were extremely inaccurate. Does anyone have an idea how I could achieve a closed function?
Many thanks
int rec(const int a, const int b, const int c = 0, const int d = 0)
{
int result = 0;
if (d == a)
++result;
else
for (int i = 0; c + i < b; ++i)
result += rec(a, b, c + i, d + 1);
return result;
}
There is no universal method of converting a recursive function to a mathematical, closed function. In your case the answer is the number of "b-1" combinations from an "a"-element set, that is, a!/((a-b+1)!(b-1)!)
.
Proof: Your rec
is equivalent to
int rec(const int a, const int b)
{
if (0 == a)
return 1;
int result = 0;
for (int i = 0; i < b; ++i)
result += rec(a - 1, b - i);
return result;
}
because all that matters is a-d and b-c.
If a==0, rec
returns 1
If a>0, it returns the sum of rec(a-1, i)
where i
is in (0, b). This is true and only true for the combinations. If you ask me to prove that, I will, but the plain text format is not good for mathematical proofs
Edit: A general idea.: print all rec(i,j)
as a table and try to spot the rule by looking at the table. I did:
for (int i = 0; i != 10 ; ++i){
for (int j = 0; j != 10; ++j){
cout << rec(i, j) << "\t";
}
cout << endl;
}
In this way I spotted that it is the Pascals_triangle