CODEWITHSUNDEEP
c++mathematical-expressions
john
john

Reputation: 23

How can I convert the given code to a mathematical function?

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;
}

Upvotes: 2

Views: 282

Answers (2)

Botond Horv&#225;th
Botond Horv&#225;th

Reputation: 1017

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

Upvotes: 4

zkoza
zkoza

Reputation: 2869

I will give a hint how you could have guessed the result yourself, with the stress on guess.

Take the sequence for rec(i, 6), i = 0,...,10. This is the sequence that you had already investigated. The answer is:

1 6 21 56 126 252 462 792 1287 2002

Now, insert it into Google (I don't know if other search engines can do the trick; Google certainly can). The first result should point you to this famous online encyclopedia:

https://oeis.org/A000389

This the Online Encyclopedia of Integer Sequences! Now, read the description:

A000389 Binomial coefficients C(n,5).

You may be not familiar with the C(*,*) notation, but you can easily understatand its "Binomial coefficient" description.

You certainly notice the relation between 6 in your function and 5 in the answer formula, but to be sure you can repeat your experiment for several other numbers other than 6.

The next step is to see how the A000389 sequence looks like:

0, 0, 0, 0, 0, 1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, ...

Well, C(i,j) is undefined (or zero, depending on the convention) if i < j. Aha! A000389 is this:

C(0,5) = 0, C(1,5) = 0, ... , C(4,5) = 0, C(5,5) = 1, C(6,5) = 6,...

This is your sequence if you started from the term of index 5, if we start counting from 0.

res(0,6) = C(5,5), res(1,6) = C(6,5),..., res(k, 6) = C(5+k, 5)

You can generalize it to

res(k, j) = C(k + j - 1, j -1)

and then start thinking how to prove it in a mathematically strict way. The usual method is by mathematical induction - I'll skip it.

This final result is already given by @Botond_Horwath, I just show to you the magic of Google search engine + the OEIS website. (If you know the latter, the former is redundant).

Upvotes: 1

Related Questions