Оптимизация рекурсии

[Dmitry_Web]

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

int factorial( int );
int factorial_1( int );
int factorial_2( int );

void main()
{
	int n;

	cout << "Vvedite chislo: ";
	cin >> n;

	cout << "Factorial " << n << " raven: " << factorial( n ) << "   " <<
		factorial_1( n ) << "   " <<
		factorial_2( n ) << endl;

}


int factorial( int n )
{
	if( n == 0 )
		return 1;
	else return n * factorial( n - 1 );
}

// В 2 раза меньше вызовов
int factorial_1( int n )
{
	if( n <= 1 )
		return 1;
	else return n * ( n - 1 ) * factorial( n - 2 );
}

// В 3 раза меньше вызовов
int factorial_2( int n )
{
	if( n <= 1 )
		return 1;
	else 
	{
		if( n == 2 )
			return 2;
		else return n * ( n - 1 ) * ( n - 2 ) * factorial( n - 3 );
	}
}

Я думаю из кода всё понятно, но дело вот в чём:
- максимальный факториал у всех функций 33 считается неправильно, да и другие( не все конечно, но всё же ) неправильно.
-factorial_1 и factorial_2 должны считать " дальше ", не так ли?

[astecenko]

Типы данных С++

[Dmitry_Web]

Сообщение от astecenko

Типы данных С++

Факториал всегда же int.

[Somebody]

Ага, особенно 33! = 86833176188118864955181944012800000 00.

[Artem_Kokos]

Ну почему же int, используйте double и вы сможете считать факториалы чисел вплоть до 170! . Конечно тогда придется учесть т.н. защиту от дурака. А еще почитайте на википедии статью о факториалах, там вроде помню выводили формулу, в которую просто подставляешь число и получаешь факториал. Я ее даже проверял в программе. Но ошибку она дает куда большую, чем первая фунция в этом коде, зато и числа по-моему больше 170! считает.

Кстати на правильность наверное не стоит грешить, машина не может считать факториалы (ровно как и все остальное) с точностью до верного. С очень большими и очень маленькими числами всегда возникают проблемы, это связано с представлением числа в машине. Попробуйте, к примеру, в типе float от числа 123456789 отнять число 123456788 - машина ответит: 8. В double такой проблемы не возникнет, но возникнет с числом еще большим этого.

[Kostia]

unsigned long long int x = 0xFFFFFFFFFFFFFFFF;
cout << x << " ";

Но и этого будет мало!
Тут нужно использовать длинную арифметику, если хотите получить точные результаты
Если нужны приблизительные значения, то long double или double подойдут

#include <iostream>
#include <limits>
int main()
{
    std::cout << std::numeric_limits<long double>::max() << std::endl;
    return 0;
}

Но в Visual Studio, long double синоним double, во многих других компиляторах long double 10 байт

[Artem_Kokos]

long double? ого...