Collatz Rekursion in C Endlosschleife

Question

Die Antwort ist wahrscheinlich blendend offensichtlich, aber für das Leben von mir kann ich es nicht sehen. Ich versuche herauszufinden, wie viele Iterationen es dauert, bis eine vom Benutzer gelieferte positive Ganzzahl auf 1 konvergiert (d.h. die rekursive Funktion ist f (x) = x/2, wenn x gerade, 3x + 1, wenn x ungerade). Die Antwort ist trivial, wenn sie mit roher Gewalt durchgeführt wird (d. H. Durch eine Reihe von if-Anweisungen). Ich strebe jedoch für einen rekursive Ansatz, und bin in einer Endlosschleife stecken:

#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; 
} 

Das Problem tritt auf, wenn die Anzahl = 1. Anstatt die Schleife zu beenden, fährt sie fort und so oszilliert sie unbegrenzt zwischen 1 und 2.

Answer 1

Die Anweisung while (number != 1) wird niemals als falsch ausgewertet, so dass Sie in einer Endlosschleife stecken bleiben, wenn Sie number != 1 übergeben.

Wie für die Berechnung der "Länge", übergeben Sie Wert, also berechnet die Funktion nicht die Anzahl der Collatz-Iterationen erforderlich, um 1 zu erhalten. Stattdessen nur eins plus die Anzahl der Collatz-Iterationen für die geeigneter Nachfolger der Nummer. Zum Beispiel ist die Anzahl von Collatz-Iterationen, die für eine Nummer n erforderlich sind, 1 plus die von einem geeigneten rekursiven Aufruf zurückgegebene Zahl, entweder n/2 oder 3*n+1, abhängig davon, ob n gerade oder ungerade ist.

Dies funktioniert:

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

Ich bin einverstanden mit @blazs. Beachten Sie, dass Sie innerhalb der while-Schleife die Variable number nicht ändern, so dass die while-Schleife bei der Rekursionswiederholung an die aufrufende Funktion die lokale Kopie der Variablennummer (die sich nicht geändert hat) erneut auswertet und dann die while-Schleife behält gehen für immer ..

Answer 3

auch dies funktioniert, Abhilfe für den Umfang Problem eine Kopie der Variablen an die Funktion der Weitergabe:

#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; 
}