Рекурсия Collatz в бесконечном цикле C

Question

Ответ, вероятно, ослепительно очевидный, но для жизни меня я не вижу. Я пытаюсь выяснить, сколько итераций требуется для того, чтобы положительное целое число, равное пользователю, сходилось к 1 (т. Е. Рекурсивная функция: f (x) = x/2, если x четный, 3x + 1, если x нечетный). Ответ тривиален, если выполняется грубая сила (т. Е. Через ряд утверждений 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; 
} 

Проблема возникает, когда число = 1. Вместо завершения цикла он продолжается и поэтому колеблется между 1 и 2 бесконечно.

Answer 1

Заявление while (number != 1) никогда не будет оцениваться как ложное, поэтому вы застряли в бесконечном цикле всякий раз, когда вы проходите number != 1.

Что касается вычисления «длины», вы передаете значение, поэтому функция не будет вычислять количество итераций Collatz, необходимых для перехода к 1. Вместо этого просто верните один плюс число итераций Collatz для соответствующий преемник этого числа. Например, количество итераций Collatz, необходимых для числа n, равно 1, плюс номер, возвращаемый подходящим рекурсивным вызовом, либо на 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

I'm согласен с @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; 
}