C++ Pascal's triangle

Question

I'm looking for an explanation for how the recursive version of pascal's triangle works

The following is the recursive return line for pascal's triangle.

int get_pascal(const int row_no,const int col_no)
{
    if (row_no == 0)
    {
        return 1;
    }
    else if (row_no == 1)
    {
        return 1;
    }
    else if (col_no == 0)
    {
        return 1;
    }
    else if (col_no == row_no)
    {
        return 1;
    }
    else
    {
        return(get_pascal(row_no-1,col_no-1)+get_pascal(row_no-1,col_no));
    }
}

I get how the algorithm works What I wonder is how the recursion does the work.

Answer 1

Your algorithm contains a couple of unnecessary predicates for the base cases. It can be stated more simply as follows:

int pascal(int row, int col) {
  if (col == 0 || col == row) {
    return 1;
  } else {
    return pascal(row - 1, col - 1) + pascal(row - 1, col);
  }
}

This of course assumes that you're guaranteeing that the arguments passed to the function are non-negative integers; you can always include an assertion if you can't impose such a guarantee from outside the function.

Answer 2

Pascal's triangle is essentially the sum of the two values immediately above it....

           1
         1   1
       1   2   1
     1   3   3   1

etc

• In this, the 1's are obtained by adding the 1 above it with the blank space (0)
• For code, all the 1's are occupied in either the first column (0), or when the (col == row)

For these two border conditions, we code in special cases (for initialization). The main chunk of the code (the recursive part) is the actual logic.

(The condition 'row == 1' is not necessary)

Answer 3

The most optimized way is this one:

int pascal(int row, int col) {
  if (col == 0 || col == row) return 1;
  else if(col == 1 || (col + 1) == row) return row;
  else return pascal(row - 1, col - 1) + pascal(row - 1, col);
}

Unlike Fox's algorithm it prevents recursive calls for values which can be easily computed right from the input values.