I don't understand how the collatz(n) recursive function works

Question

If you watch the short on recursion in week2 2018, Doug explains how calculate the steps for the collatz conjecture. I don't understand how the solution he proposes can work:

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

Here's how I understand it: say n == 2, the first condition proves false, the second proves true, we call collatz(n) again and this time the first condition proves true. To me, this function should always return 0 but it works correctly, giving the correct result(1 in this case). Can anybody explain how?

Answer 1

Based on the Collatz Conjecture, all values of n will eventually reach the value of 1 and fall into the pattern of 1, 4, 2, 1, 4... continuing forever. Therefore we want to have a base condition to detect when the input value is equal to 1. The code that checks for this is:

if(n == 1)
    return 0;

The next step to check is if the value that has been input is even or odd (n % 2 == 0 will return true if n is even and false if n is odd).

If the value is even, based on the Collatz Conjecture, we divide by two. This is completed by the code:

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

This is basically saying, "If the number is even, take a step by dividing by 2 and calculate the number of steps it takes for that number."

If the value is odd (not even, hence the else), the Collatz Conjecture tells us to multiply by 3 and add 1. The code for this is:

else
    return 1 + collatz(3 * n + 1);

The interpretation of this is, "If the number is odd, take a step by multiplying by 3 and adding 1 and calculate the number of steps for the resulting number."

The 1 + collatz(...) is taking the step you just took, represented by the 1, and then adding the number of steps (calculated recursively) that the resulting number will take.

For example, collatz(5) will result in the recursive method returning 1 + collatz(16) + collatz(8) + collatz(4) + collatz(2) + collatz(1)

or,

1 + 1 + 1 + 1 + 1 + 0 = 5

This tells you that it takes 5 steps to complete the Collatz Conjecture for the value 5.

Answer 2

I think I just got it. I thought that when you hit the line return 0; it just returns that value into main. But the value is returned just where the function has been called. So in this case, 0 is the result of calling collatz of 2 / 2. And the result of return 1 + collatz(n / 2); then must be 1 + 0 == 1 Do I understand it correctly?

Answer 3

I tried this function before Doug's explanation. I added a user input and a variable "steps" to store how many steps were taken. It seems to work besides when I call collatz(1). It returns 0 steps and there should be at least 1 step.. Here is my code:

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

int collatz(int n);

int steps = 0;
int main(void)
{
    int num = get_int("Write a number: ");
    collatz(num);
    printf("The number of steps is %i\n", steps);
}

// Does not work properly. if the number introduced is 1, shows 0 steps..

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

Any ideas? Thanks!

Regarding the question asked by user21120, so is the program keeping track of the "returned" values somewhere? and then at the end it just sums up all those "returns"? How can I get those in main? Thanks

Answer 4

I changed the code a little. The collatz call recursively,every time, it add 1 to the return value.If (n==1) return 0; but the caller return 1+0, and so on. the code is follow:

#include <cs50.h>
#include <stdio.h>
int collatz(int n)
{
    printf("n=%i\n",n);
    if(n == 1)
    {
        return 0;
    }
    else if((n % 2) == 0)
    {
        return 1+collatz(n/2);
    }
    else
    {
        return 1+collatz(3*n + 1);
    }
 }

 int main(void)
{
    int num = get_int(" number: ");
    int steps=collatz(num);
    printf("The number of steps is %i\n", steps);
}