Проверка переполнения типа в рекурсии

[kdm]

Надо написать функцию для нахождения числа Стирлинга 2 рода(Комбинаторика)
Сама формула выглядит как S(m,n) = S(m-1, n-1) + n*S(m-1, n).

Вот так выглядит моя рекурсивная функция.
MAXANSWER = 2^32;

unsigned int S(unsigned int m,unsigned int n)
{
   unsigned int Answer = 0;
   unsigned int a, b, c;
   if (m == n)
      return 1;
   if (m > 0 && !n)
                return 0;
   if (!m && !n)
      return 1;
   if (n > m)
      return 0;
   if (!Error)
   {
      a = S(m - 1, n - 1);
      b = S(m - 1, n);
      if (b >= MAXANSWER / n)
      {
         Error = 1;
         return 0;
      }
      c = b * n;
      if (c >= MAXANSWER - a)
      {
         Error = 1;
         return 0;
      }
                Answer = a + c;
   }
   return Answer;
}

Как можно выполнить проверку переполнения a и b в этой функции?

Пользуйтесь тегом [code] // нг

[e2e4]

Эээ, Вы вроде бы уже выполнили проверку на переполнение следующим кодом:

if (b >= MAXANSWER / n) 
{ 
  Error = 1; 
  return 0; 
} 
c = b * n; 
if (c >= MAXANSWER - a) 
{ 
  Error = 1; 
  return 0; 
} 
Answer = a + c;

Что Вам еще нехватает?

Добавлено спустя 8 минут 47 секунд:

P.S. Мне ясно, что при переполнении у Вас некоторая внешняя переменная Error устанавливается в 1. Неясно только, зачем нужна проверка if (!Error), т.к. в момент провекри Error всегда 0.

[kdm]

Error - глобальная переменная, изначально равная 0, как я понимаю, когда наступит переполнение, она станет 1 и, чтобы не заходить в рекурсию, я поставил эту проверку..возможно, я ошибаюсь и она действительно лишняя..

Цитата:

Что Вам еще нехватает?

Тестирование показало, что этих проверок не всегда хватает, почему мне как раз и непонятно.

[e2e4]

Для начала используйте вместо Вашего MAXANSWER именнованную константу UINT_MAX, определенную в limits.h. У меня подозрение, что проблема в 2^32 (естественно не укладывается в 32-битное беззнаковое целое).
Далее. Рекомендую для начала завести промежуточную переменную типа unsigned long long int, проводить с ней все вычисления, проверять ее на то, что она не больше UINT_MAX, и присваивать Вашим переменным ее значение в положительном случае.

Цитата:

Error - глобальная переменная, изначально равная 0, как я понимаю, когда наступит переполнение, она станет 1 и, чтобы не заходить в рекурсию, я поставил эту проверку..возможно, я ошибаюсь и она действительно лишняя..

Посмотрите внимательно - переполнение может произойти только тогда, когда все экземпляры рекурсивной ф-ии уже вызваны, и в каждом вызове проверка на Error уже прошла.

[kdm]

да, спасибо большое, по поводу Error и UINT_MAX поправил....но с переполнением осталась бага...до определенных чисел все нормально считает и проверяет переполнение, но когда a достаточно велико бага осталась(причем абсолютно для меня непонятная, ибо проверки действительно на первый взгляд есть)

[e2e4]

kdm, Вы сделали так, как я советовал: применить в качестве хранилища промежуточных результатов вычислений unsigned long long int?

Есть подозрение, что у Вас банально переполняется стек из-за слишком большого кол-ва вызовов Вашей рекурсивной ф-ии. Попробуйте зарегестрировать использование стека Вашей программой.

[kdm]

Дествительно, так оно и есть, переполняется стек....осталось это поправить

[e2e4]

Цитата:

Дествительно, так оно и есть, переполняется стек....осталось это поправить

Успехов в поисках багов!

Почему я сразу про стек не стал писать - был уверен, что человек, применяя функцию, которая дважды вызывает сама себя на каждой итерации, твердо знает, что делает .

Вы посчитайте, как быстро она размножается ($2^n$), сколько памяти и процессорного времени на это тратится.

[kdm]

я тоже думал, что знаю спасибо