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，因此它将导致不可移植的代码。显然，您的编译器无论如何都不会优化这个特定的尾部调用。）

Answer 2

不是 C 专家，但编译器通常会强制执行调用堆栈深度限制。也许您可以使用编译器标志更改它，但这并不能解决您的问题。使算法迭代而不是递归将修复它。

通常，递归算法不会比迭代算法快。但它们通常更容易理解。 （=更优雅）

Answer 3

好吧，伙计们，
我找到了！

所以这是我的代码，我仍然使用递归，但仅用于内部循环 fung()，

我对它印象不深，因为它需要 0,5 秒来计算输入 1 和 1000000，有人的代码可以在 0 秒内完成，哈哈，

我用迭代方法改变了外循环 comp()，

看这里

#include "stdio.h"
/*#include "windows.h"*/

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

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

/*
Above recursion will looked like this in iterative method
int func(int n) {
    int c=1;
    while (n != 1) {
        c++;
        if (n % 2 == 0)
            n=n/2;
        else
            n=(n*3)+1;
    }
    return c;
}
*/

/*Outer Loop*/
int iter(int i,int j) {
    int tmp1=0,tmp2;
    while (i <= j) {
        tmp2 = fung(i,1);
        if (tmp1 < tmp2)
            tmp1 = tmp2;
        i++;
    }
    return tmp1;
}

int main() {
    unsigned int i,j,s,f;
    while (scanf("%d %d",&i,&j)) {            /*UVa Standard, infinite loop*/
        /*s = GetTickCount();*/
        printf("%d %d %d",i,j,iter(i,j));
        /*f = GetTickCount();
        printf("%lu\n",f-s);*/
    }
    return 0;
}