C Language: Recursion and the Collatz Conjecture

We continue to take the Computer Science CS50 course and the C language. We study recursion using the example of the Collatz hypothesis – an interesting (and easy to understand) mathematical problem that has not yet been solved by scientists.

Collatz hypothesis:

1. Take any positive integer
2. If it’s even, then divide it by 2
3. If odd, then multiply by 3 and add 1 (we get n * 3 + 1).
4. Next, we evaluate the resulting number again – is it even or not, and again perform the same actions until we get 1.

In total, the essence of the Collatz conjecture is that absolutely any number, when these two simple operations are applied to it, will sooner or later turn into 1.

If we look at this problem in the traditional way and try to solve it through a loop without using recursion, we get the following code (Igroglaz’s solution):

#include <stdio.h>

int collatz(int);
int main (void)
{
    int n;

    printf("Which number to Collatzinate?\n");
    scanf("%d", &n);

    printf("Number of steps for %d is %d", n, collatz(n));

    return 0;
}

int collatz(int n)
{
    int steps = 0;

    while (n != 1)
    {
        if (n % 2 == 0 && n > 1)
            n /= 2;
        else
            n = (n * 3) + 1;
        steps++;
    }

    return steps++;
}

Now let’s try to write code with recursion. We have one base case: if n is equal to 1, then it’s time to exit the recursion. And we have two recursive cases:

1. if n is even, we do one recursive case, dividing n by 2.
2. if n is odd, we do another recursive case for 3 times n plus 1.

So the goal is to write a recursive Collatz function where we pass a value of n and the function calculates how many steps it will take to get to 1. If n is 1, then 0 steps are required. Otherwise, we will take one step plus as many steps as required either for n divided by 2 if n is even, or for 3*n plus 1 if n is odd.

Here are some test values ​​to test different Collatz numbers and also to see the steps it takes to get to 1.

So, let’s try to recursively determine the Collatz number for n; to have our function calculate how many steps it takes to get to 1.

Recursion is a variant of Shtukentsia (how to count the number of steps for n, if for example n=27; you can substitute your own value in brackets):

#include <cs50.h>
#include <stdio.h>

int collatz (int n);
int steps = 0;

int main (void)
{

    int steps_number = collatz(27);
    printf ("%i\n", steps_number);

}


int collatz (int n)
{

    if (n == 1)
        return steps;

    else if (n % 2 == 0)
    {
        steps += 1;
        return collatz (n / 2);
    }

    else if (n % 2 != 0)
    {
        steps += 1;
        return collatz(3 * n + 1);
    }

    return 0;
}

Shtukensia did a great job 🙂 She heard a hint from me about a global variable. I also learned something from her. Initially, I wrote a clumsy version of the recursion that didn’t correctly exit nested functions – the error recursion from Igroglaz:

#include <stdio.h>

int collatz(int);
int steps = 0;

int main (void)
{
    int n;

    printf("Which number to Collatzinate?\n");
    scanf("%d", &n);
    printf("Number of steps for %d is", n);
    collatz(n);
    printf(" %d", steps);

    return 0;
}

int collatz(int n)
{
    if (n == 1)
        return 0;

    if (n % 2 == 0 && n > 0)
    {
        n = n / 2;
        steps++;
        collatz(n);
    }
    else
    {
        n = (n * 3) + 1;
        steps++;
        collatz(n);
    }
}

However, this code produces the correct result. After solving the problem, Shtukentsia and I exchanged chairs – so that she would look at my code, and I would look at hers. Out of the corner of my eye, I saw that it exits recursive cases through return and was surprised. But even before the exchange of chairs, I was surprised that I have a very strange return steps if (n == 1) return steps; – gives out some five-digit values, although the number of steps according to the debugger is correct. That’s why I changed steps to 0 and displayed pure steps in main in the first version of the program;)

I started debugging and in the process I realized that I don’t exit recursive functions, but leave them hanging … I remembered Shtukentsia’s return (oh, sorry, I spied it by accident, and didn’t think of it myself). As a result, here is the correct version of the recursion from Igroglaz:

#include <stdio.h>

int collatz(int);
int steps = 0;

int main (void)
{
    int n;

    printf("Which number to Collatzinate?\n");
    scanf("%d", &n);
    printf("Number of steps for %d is %d", n, collatz(n));

    return 0;
}

int collatz(int n)
{
    if (n == 1)
        return steps;

    if (n % 2 == 0 && n > 0)
    {
        n = n / 2;
        steps++;
        return collatz(n);
    }
    else
    {
        n = (n * 3) + 1;
        steps++;
        return collatz(n);
    }
}

I never thought that the humanists could handle such things 🙂 Nevertheless, Shtukentsia and I are two humanitarians. And everything works out. So you will be fine too!