c - 递归 collat​​z 实现的意外错误

Question

编辑:当我将代码上传到自动测试平台时，程序不会在那里崩溃 - 它返回正确的结果，但花费的时间太长(超过 5 秒)...wtf...

对于大学，我必须实现一个函数，该函数返回从输入到达到 1 所采取的步数，遵循 collat​​z 猜想。猜想非常简单——给定任意整数:

1.如果是偶数 - 除以二 (n/2)

2.如果是奇数 - 乘以 3 并加一 (n*3+1)

猜想是所有数字最终都会达到1。我们不必证明或检查这一点，我们只需要返回给定数字所采取的步骤即可。

我们以前做过这个问题，但这次我们必须检查更大的数字(他们指定使用 long 而不是 int)并且使用递归。他们给了我们骨架代码，并要求我们只实现功能 - 所以我所有的代码都包含在里面

int lengthCollat​​z(long n) {//mycode }

main 中的骨架代码收集两个输入值 - a 和 b，其中 a < b <100000000。它检查 a 和 b 之间的每个数字按照 collat​​z 序列到达 1 需要多少步，然后返回所采取步数最多的数字。

我添加的函数似乎工作得很好，但在较大的值(当输入 2 以百万计)时，它似乎无缘无故地崩溃并且没有给出任何错误。我已经尝试将所有内容更改为无符号长整型甚至长整型以查看是否有溢出 - 在这种情况下程序会卡住......我不明白出了什么问题，请帮助我诊断错误。附言我怎样才能提高这些计算的速度？我们有 5 秒的限制。

我所有的代码都在 lengthCollat​​z 函数中(以及它上面的 length 全局变量)你能找出问题所在吗？

#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，它工作正常，但速度很慢。在我的普通 PC 上 29 秒。优化版本通过在可以预先计算结果时不调用自身来运行快两秒，但该版本接近于手动循环展开。前者:

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);
}

当然还有其他方法可以解决这个问题，但是要在五秒内完成？如果找到解决方案，请发布解决方案。