CODEWITHSUNDEEP
crecursioncollatz
andreithegiant
andreithegiant

Reputation: 217

Collatz recursion in C infinite loop

The answer is probably blindingly obvious but for the life of me I can't see it. I am trying to find out how many iterations it takes for a user-supplied positive integer to converge to 1 (i.e. recursive function is f(x)=x/2 if x even, 3x+1 if x odd). The answer is trivial if done brute force (i.e. through a series of if statements). I am however aiming for a recursive approach, and am stuck in an infinite loop: 

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

The problem occurs when number=1. Instead of the loop terminating, it continues and so it oscillates between 1 and 2 indefinitely.

Upvotes: 0

Views: 1710

Answers (3)

andreithegiant
andreithegiant

Reputation: 217

This works too, workaround to the scope problem of passing a copy of variables to the function:

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

Upvotes: 0

blazs
blazs

Reputation: 4845

The statement while (number != 1) will never evaluate to false, so you're stuck in an infinite loop whenever you pass number != 1.

As for computing the "length," you're passing by value, so the function won't compute the number of Collatz iterations needed to get to 1. Instead, just return one plus the number of Collatz iterations for the appropriate successor of the number. For example, the number of Collatz iterations required for a number n is 1 plus the number returned by a suitable recursive call, either on n/2 or 3*n+1, depending on whether n is even or odd, respectively.

This will work:

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

Upvotes: 3

V.moreno
V.moreno

Reputation: 44

I´m agree with @blazs. Notice that within the while loop you don´t actually modify the variable number so when the recursion rollback to the caller function, the while loop will evaluate the LOCAL copy of variable number again (which has not change) and then the while loop will keep going forever..

Upvotes: 0

Related Questions