UVa 3n + 1案例递归堆栈溢出

Question

我试图解决这个第一个挑战,但我卡住了,我喜欢快速程序,所以我决定使用递归方法而不是迭代

不幸的是,当输入是一个大整数(100000>输入> 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,因此它将导致不可移植的代码.显然,您的编译器无论如何都不会优化此特定的尾调用.)