c - UVa 3n+1 情况递归堆栈溢出

Question

我试图解决这个第一个挑战，但我陷入困境，我喜欢快速程序，所以我决定使用递归方法而不是迭代

不幸的是，当输入是一个大整数时(100000 > input > 1000000)，它经常崩溃

所以我调试它，它显示堆栈溢出错误

请帮助我，我不知道该怎么办，我尝试将数据类型更改为 unsigned long、unsigned int 等，但都不起作用

这是我的代码，我使用 ANSI C

#include "stdio.h"

int cek(int n) {
    return n % 2;
}

int fung(int n,int c) {
    if (n == 1) {
        return c;
    }
    if (!cek(n)) {
        return fung(n/2,++c);
    }
    else {
        return fung((n*3)+1,++c);
    }
}

int comp(int i,int j,int tmp) {
    int temp;
    if (i == j)
        return tmp;
    temp = fung(i,1);
    if (temp > tmp)
        return comp(++i,j,temp);
    else
        return comp(++i,j,tmp);
}

int main() {
    int i,j,tmp;
    while (scanf("%d %d",&i,&j)) {
        if (i > j) {
            tmp = i;
            i = j;
            j = tmp;
        }
        printf("%d %d %d\n",i,j,comp(i,j,0));
    }
    return 0;
}

PS:抱歉我的愚蠢，我真的是新手@_@

Answer 1

递归不太可能比迭代更快，事实上它可能会更慢。

调用堆栈的大小是有限的，如果你的递归比这个更深，你就无能为力了。特别是在 Collat​​z 问题中，无法预先知道需要多少步。使用迭代方法重写它。

(如果您的编译器进行尾部调用优化，递归可能仍然有效。但是标准不要求 TCO，因此它将导致不可移植的代码。显然，您的编译器无论如何都不会优化这个特定的尾部调用。)