c++mathematical-expressions

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

Solution

  • 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