Pascal's Triangle

[nand]

Hi,
I made a Pascal's Triangle practice problem listed below.
I want to ask:
1. What protection can I implement to stop the program when the result overflows? (when requesting a high value, eg. line 100, column 50 )
2. What can be done to make the program execution speed up? Because many of the recursive values are calculated more than once... some form of binary tree?

Thank you!

/*
 * Write a program to compute the value of a given position in Pascal's 
Triangle (See image).

The way to compute any given position's value is to add up the numbers to the
 position's right and left in the preceding row. For instance, to compute the 
middle number in the third row, you add 1 and 1; the sides of the triangle are
 always 1 because you only add the number to the upper left or the upper right 
(there being no second number on the other side).
The program should prompt the user to input a row and a position in the row. 
The program should ensure that the input is valid before computing a value for 
the position.
 */


#include <iostream>
using namespace std;

unsigned long int pascal (int row, int col)
{
	if ( col == 0 )
		return 1;
	else if ( row == 0)
		return 1;
	else if ( col == row  )
		return 1;

	return ( pascal ( --row, --col ) + pascal ( row , ++col) );
	// row gets decremented in first function call, and remains so for the seccond
	// col gets decremented at the first func. call, and has to be incremented for the seccond

}

int main(int argc, char** argv)
{ cout << endl<<endl;

	cout << "\n Pascal's triangle: ";
	cout << "\n 1 ";
	cout << "\n 1 1 ";
	cout << "\n 1 2 1 ";
	cout << "\n 1 3 3 1 ";
	cout << "\n 1 4 6 4 1 ";
	cout << "\n 1 5 10 10 5 1 ";

	int row, col;
	row = 0;
	col = 0;
	do
	{
	cout << "\n \n please enter the row (starting from 0) : "; cin >> row;
	cout << "\n please enter the column (starting from 0) : "; cin >> col;
	}
	while ( row < 0 || ( col > row  ) );

	cout << "\n \n the pascal triangle value is : "<< pascal ( row, col ) <<" have a nice day";



	cout << endl<<endl;
	return 0;

}

[m4ster r0shi]

For #1, check this out -> http://www.cplusplus.com/forum/lounge/32041/

For #2, check this out:

#include <iostream>
#include <map>

typedef unsigned long RetType;
typedef unsigned int  ArgType;

RetType pascal (ArgType row, ArgType col)
{
    typedef std::pair<ArgType, ArgType> Pos;
    typedef std::map<Pos, RetType> PascalCache;

    static PascalCache pascal_cache;

    if ( col ==   0 ) return 1;
    if ( row ==   0 ) return 1;
    if ( col == row ) return 1;

    PascalCache::const_iterator it;
    Pos cur_pos(row, col);
    RetType ret;

    it = pascal_cache.find(cur_pos);

    if (it != pascal_cache.end())
        ret = it->second;
    else
    {
        ret = pascal ( --row, --col )
            + pascal (   row, ++col );

        pascal_cache[cur_pos] = ret;
    }

    return ret;
}

int main()
{
    std::cout << pascal(32, 16) << std::endl;
}

[nand]

hi,

Thank you for your post.
I didn't know about maps at all. I tryed your program and it works much better than mine. Thanks for lighting my way. :D