C++ Pascal's triangle

Question

Hello, 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

Pascal's triangle can be got from adding the two entries above the current one.

  | 0          1          2          3            column
--+----------------------------------------------
0 | 1 (case 1)
1 | 1 (case 2) 1 (case 2)
2 | 1 (case 3) 2 (sum)    1 (case 4)
3 | 1 (case 3) 3 (sum)    3 (sum)    1 (case 4)

row

etc., for example column 2, row 3 = column 2, row 2 + column 1, row 2, where the cases are as follows:

if (row_no == 0) // case 1
{
    return 1;
}
else if (row_no == 1) // case 2
{
    return 1;
}
else if (col_no == 0) // case 3
{
    return 1;
}
else if (col_no == row_no) // case 4
{
    return 1;
}
else // return the sum
    return pascalRecursive(height-1,width)+pascalRecursive(height-1,width-1);

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

Here is how the recursion works

We call v(i, j), it calls v(i - 1, j), which calls v(i - 2, j) and so on, 
until we reach the values that are already calculated (if you do caching), 
or the i and j that are on the border of our triangle.

Then it goes back up eventually to v(i - 1, j), which now calls v(i - 2, j - 1), 
which goes all the way to the bottom again, and so on.   

....................................................................
                  _ _ _ _ call v(i, j) _ _ _ _ _
                 /                              \ 
                /                                \
               /                                  \   
           call v(i - 1, j)                     v(i - 1, j - 1)
         /                 \                   /               \
        /                   \                 /                 \
 call v(i - 2, j)  v(i - 2, j - 1)    v(i - 2, j - 1)    v(i - 2, j - 2)
....................................................................

If you need to get the value often, and if you have enough memory:

class PascalTriangle
  # unlimited size cache

  public 

  def initialize
    @triangle = Array.new  
  end

  def value(i, j)
    triangle_at(i, j)
  end

  private

  def triangle_at(i, j)
    if i < j
      return nil 
    end

    if @triangle[i].nil?        
      @triangle[i] = Array.new(i + 1)
    else
      return @triangle[i][j]
    end

    if (i == 0 || j == 0 || i == j)
      @triangle[i][j] = 1
      return @triangle[i][j]
    end

    @triangle[i][j] = triangle_at(i - 1, j) + triangle_at(i - 1, j - 1)
  end
end