C++ Pascal's triangle

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 w开发者_开发问答orks What I wonder is how the recursion does the work.

---

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.

---

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)

---

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.

---

Refer to the page for the source code:

#include <stdio.h>
int main()
{
  int n, x, y, c, q;
  printf("Pascal Triangle Program\n");
  printf("Enter the number of rows: ");
  scanf("%d",&n);

  for (y = 0; y < n; y++)
  {
        c = 1;
        for(q = 0; q < n - y; q++)
        {
              printf("%3s", " ");
        }
        for (x = 0; x <= y; x++)
        {
              printf("   %3d ",c);
              c = c * (y - x) / (x + 1);
        }
        printf("\n");
  }
  printf("\n");
  return 0;
  }

The output would be,

Pascal Triangle Program

Enter the number of rows: 11

                                  1

                               1      1

                            1      2      1

                         1      3      3      1

                      1      4      6      4      1

                   1      5     10     10      5      1

                1      6     15     20     15      6      1

             1      7     21     35     35     21      7      1

          1      8     28     56     70     56     28      8      1

       1      9     36     84    126    126     84     36      9      1

    1     10     45    120    210    252    210    120     45     10      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);

---

Here is the code of @kathir-softwareandfinance with more readable and more meaning variable names

#include <stdio.h>

int main()
{
  int nOfRows, cols, rows, value, nOfSpace;
  printf("Pascal Triangle Program\n");
  printf("Enter the number of rows: ");
  scanf("%d",&nOfRows);

  for (rows = 0; rows < nOfRows; rows++)
  {
    value = 1;
    for(nOfSpace = 0; nOfSpace < nOfRows - rows; nOfSpace++)
    {
        printf("%3s", " ");
    }

    for (cols = 0; cols <= rows; cols++)
    {
        printf("  %3d ",value);
        value = value * (rows - cols) / (cols + 1);
    }
    printf("\n");
  }
  printf("\n");

  return 0;
}

---

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

---

Using ternary approach for optimization; only 1 return command needed.

int f(int i, int j) {
    return (
       (i <= 1 || !j || j == i) ? 1 :
       (f(i - 1, j - 1) + f(i - 1, j))
    );
}

see explanation