Collatz Conjecture

[stdq]

I tried implementing a recursive function for the Collatz conjecture. If the function eventually returns 1, then we have a success. The main function tests the conjecture for all natural numbers between 1 and 1000, including. However, I suspect this recursive solution, even if correct, might be bound to cause a stack overflow. You can read about this conjecture here: http://en.wikipedia.org/wiki/Collatz_conjecture. The program, when executed, printed 1000 successes, although that doesn't prove that the conjecture might succeed with larger numbers. And, again, I'm not completely certain my implementation is correct.

#include <stdio.h>

int f( int n );

int main( void )
{
    int i;
    int numberOfSuccesses = 0;
    
    for ( i = 1 ; i <= 1000 ; ++i )
    {
        if ( f( i ) == 1 )
        {
            ++numberOfSuccesses;
        }
    }
    
    printf( "Number of successes for %d natural numbers: %d.\n", ( i - 1 ), numberOfSuccesses );
     
    return 0;
}

int f( int n )
{
    if ( n == 1 )
    {
        return 1;
    }
    
    if ( n % 2 == 0 )
    {
        return f( n / 2 );
    }
    
    return f( 3 * n + 1 );
}

[weaknessforcats]

Any recursion can be written as a loop.

Recursion is not a necessary programming construct but it does allow for elegant solutions to some problems. It is always slower than a loop and may cause stack overflow on some systems.