Recursion: Collatz sequence -Could someone please explain how this code returns the total number of-CodePudding

#include <cs50.h>

int collatz(int n);

int main(void)
{
    int n = get_int("Enter int: ");
    int steps = collatz(n);
    printf("%i\n", steps);
}

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

I am geting stuck trying to visualise how the 'return 1' on each iteration of the function gets 'carried through'.

I can write the steps out on paper to show that it does work, however I am struggling to make clear in my mind without going through step-by-step, why you have to 1 on every iteration of collatz.

CodePudding user response：

This code:

    if (n==1)
    {
        return 0;
    }

says: If there are no steps to perform (because n is already 1), return zero.

Otherwise, this code:

    else if ((n%2)==0)

selects one of the following:

        return 1   collatz(n/2);

or:

        return 1   collatz(3 * n   1);

Each of those performs one step (either n/2 or 3 * n 1) and then calls collatz to find out how many steps it takes to finish with that value. When collatz returns the number of steps needed for n/2 or 3 * n 1, this code adds one for the step performed here. That gives the number of steps needed for n, which this code then returns.

CodePudding user response：

Try to visualize it as follows:

starting number: 3

** collatz(3): return 1   collatz(10); **

collatz(10): return 1   collatz(5);

** collatz(3): return 1   (1   collatz(5)); **

collatz(5): return 1   collatz(16);

** collatz(3): return 1   (1   (1   collatz(16))); **

collatz(16): return 1   collatz(8);

** collatz(3): return 1   (1   (1   (1   collatz(8)))); **

collatz(8): return 1   collatz(4);

** collatz(3): return 1   (1   (1   (1   (1   collatz(4))))); **

collatz(4): return 1   collatz(2);

** collatz(3): return 1   (1   (1   (1   (1   (1   collatz(2)))))); **

collatz(2): return 1   collatz(1);

collatz(1): return 0;

** collatz(3): return 1   1   1   1   1   1   1   0; **