C无限循环中的Collatz递归

Question

答案可能显而易见，但就我而言，我看不到它。我试图找出用户提供的正整数收敛到 1 需要多少次迭代（即如果 x 为偶数，则递归函数为 f(x)=x/2，如果 x 为奇数，则为 3x+1）。如果使用蛮力（即通过一系列 if 语句），答案是微不足道的。然而，我的目标是递归方法，并且陷入了无限循环：

#include <stdio.h>

int collatz(long number, int length)    
{

    while (number != 1)
    {
        length++;
        printf("%ld\n", number);
        if ((number % 2) == 0)
            collatz(number/2,length);
        else
            collatz(3*number+1,length);
    }

    return length;
}
int main()  
{
    long number;
    printf("Input a number\n");
    scanf("%ld", &number);
    int length=1;
    printf("length is %d", collatz(number,length));
    return 0;
}

number=1时出现问题。它没有终止循环，而是继续，因此它无限期地在 1 和 2 之间振荡。

Answer 1

语句 while (number != 1) 永远不会计算为 false，因此每当您通过 number != 1.

时，您就会陷入无限循环

至于计算 "length," 你是按值传递的，所以该函数不会计算达到 1 所需的 Collatz 迭代次数。相反，只是 return 一加数字的适当后继者的 Collatz 迭代次数。例如，数字 n 所需的 Collatz 迭代次数是 1 加上数字 return 通过合适的递归调用编辑的数 n/2 或 3*n+1，具体取决于n 分别是偶数还是奇数。

这会起作用：

int collatz(long number)    
{
    if (number != 1)
    {
        printf("%ld\n", number);
        if ((number % 2) == 0)
            return 1+collatz(number/2);
        else
            return 1+collatz(3*number+1);
    }

    return 0;
}

Answer 2

我同意@blazs。请注意，在 while 循环中，您实际上并没有修改变量号，因此当递归回滚到调用函数时，while 循环将再次评估变量号的本地副本（未更改），然后 while 循环将保持永远..

Answer 3

这也有效，解决将变量副本传递给函数的范围问题：

    #include <stdio.h>

int collatz(long number, int length)    
{
    int temp=number;    
    int templength=length;  
    while (temp!= 1)
    {
        templength++;
        printf("%ld\n", number);
        if ((temp% 2) == 0)
            return collatz(temp/2,templength);
        else
            return collatz(3*temp+1,templength);
    }

    return templength;
}
int main()  
{
    long number;
    printf("Input a number\n");
    scanf("%ld", &number);
    int length=1;
    printf("length is %d", collatz(number,length));
    return 0;
}

C无限循环中的Collatz递归

Collatz recursion in C infinite loop

c

recursion

collatz

C无限循环中的Collat​​z递归

Collatz recursion in C infinite loop

c

recursion

collatz

C无限循环中的Collatz递归