Неожиданная ошибка для рекурсивной реализации collatz

Question

EDIT: Когда я загружаю код на платформу автоматического тестирования, программа не падает там - она ​​возвращает правильный результат, но занимает слишком много времени (превышает 5 секунд) ... wtf. ..

Для университета я должен реализовать функцию, которая возвращает количество шагов, взятых из ввода, чтобы достичь 1, следуя гипотезе collatz. Гипотеза очень проста - дано любое целое число:

1. Если это даже - разделить его на два (N/2)

2. Если нечетное - времена это на 3 и добавьте один (n * 3 + 1)

Догадка заключается в том, что все числа в конечном итоге достигнут 1. Нам не нужно доказывать или проверять это, нам просто нужно вернуть шаги, предпринятые для данного номера.

Мы уже делали эту проблему раньше, но на этот раз мы должны проверить гораздо большие числа (они указывают, чтобы использовать long вместо int) И использовать рекурсию. Они дали нам скелет кода, и попросили нас реализовать только функцию - так что все мой код, содержащийся внутри

Int lengthCollatz (длинный п) {// mycode}

скелет кода в main собирает два входных значения - a и b, где a < b < 100000000. Он проверяет, сколько шагов требуется для каждого числа между a и b, следуя последовательности collatz, чтобы достичь 1, а затем возвращает число с наибольшей суммой предпринятых шагов.

Функция, которую я добавил, кажется, работает отлично, но при больших значениях (когда вход 2 находится в миллионах), он, кажется, падает без причины и не дает никаких ошибок. Я попытался изменить все на unsigned longs и даже на долгое время, чтобы увидеть, что что-то переполнено - в этом случае программа просто застревает ... Я не понимаю, что случилось, пожалуйста, помогите мне диагностировать ошибку. Постскриптум Как я могу улучшить скорость этих вычислений? У нас есть предел в 5 секунд.

Весь мой код находится внутри функции lengthCollatz (и глобальной переменной длины чуть выше нее). Вы можете определить проблему?

#include <stdio.h> 
#define MAX64 9223372036854775807L /* 2ˆ63 -1 */ 

int length = 0; 

int lengthCollatz(long n) { 
    length++; 
    //if not 1 
    if(n!=1){ 
     //if odd 
     if(n&1) { 
      lengthCollatz(n=n*3+1); 
     } 
     //if even 
     else { 
      lengthCollatz(n/=2); 
     } 

    } 
    //if reached n = 1 
    else { 
     //return amount of steps taken 
     int returnLength = length; 
     length = 0; 
     return returnLength; 
    } 
} 
int main(int argc, char *argv[]) 
{ 

int n, a, b, len=-1; 

scanf ("%d %d", &a, &b); 

while (a <= b) { 

    int l = lengthCollatz(a); 
     if (l > len) { 
      n = a; 
      len = l; 
     } 
     a++; 
} 
printf("%d\n", n); 
return 0; 
} 

Обновлено функция:

int lengthCollatz(long n) { 
 
     if(n==1){ 
 
      //return depthRecursion; 
 
     } 
 
     else { 
 
      if(n&1) { 
 
       n=n*3+1; 
 
      } 
 
      else { 
 
       n/=2; 
 
      } 
 
      return lengthCollatz(n); 
 
     } 
 
}

Answer 1

Вот одна альтернативная версия, которая не сегментации для диапазона входного сигнала задается OP:

int collatz(unsigned long n) 
{ 
    if (n == 1) 
     return 1; 
    else if (n & 1) 
     return 1 + collatz(n * 3 + 1); 
    else 
     return 1 + collatz(n >> 1); 
} 

AFAICT, это работает Хорошо, но это очень медленно. 29 секунд на моем посредственном ПК. Оптимизированная версия запускается на две секунды быстрее, не вызывая себя, когда результат может быть предварительно вычислен, но эта версия граничит с разворачиванием ручного цикла. FWIW:

int collatz(unsigned long n) 
{ 
    if (n == 1) 
     return 1; 

    if (n & 1) 
     return 2 + collatz((n * 3 + 1) >> 1); 

    // Is n dividable by 16? 
    if (n & 0xF == 0) 
     return 4 + collatz(n >> 4); 

    // Is n dividable by 8? 
    if (n & 0x7 == 0) 
     return 3 + collatz(n >> 3); 

    // Is n dividable by 4? 
    if (n & 0x3 == 0) 
     return 2 + collatz(n >> 2); 

    return 1 + collatz(n >> 1); 
} 

Есть, конечно, и другие способы, чтобы решить эту проблему, но, чтобы закончить через пять секунд? Отправьте решение, если найдете его.