Intermediate Exercism • csharp

Collatz Conjecture

Challenge Overview

Calculate the number of steps to reach 1 using the Collatz conjecture.

Visit the collatz-conjecture exercise on Exercism to read the full instructions and download the exercise files.

Dig Deeper

while loop

`while` loop

using System;

public static class CollatzConjecture
{
    public static int Steps(int number)
    {
        if (number <= 0)
            throw new ArgumentOutOfRangeException(nameof(number));

        var currentNumber = number;
        var stepCount = 0;

        while (currentNumber != 1)
        {
            if (currentNumber % 2 == 0)
                currentNumber = currentNumber / 2;
            else
                currentNumber = currentNumber * 3 + 1;

            stepCount++;
        }

        return stepCount;
    }
}

The first step is to check the number parameter for validity:

if (number <= 0)
    throw new ArgumentOutOfRangeException(nameof(number));

We then define two variables:

currentNumber: contains the current number in the sequence as a result of repeated application of the algorithm (with its starting value being the number parameter)
stepCount: keeps track of the number of steps (which is the number of times we apply the algorithm)

var currentNumber = number;
var stepCount = 0;

Re-assiging values to a parameter _is_ possible, but it is considered good practice to not do that.

Then a while loop starts by checking whether the current number is not equal to 1; if it is, the method terminates:

while (currentNumber != 1)

Within the loop, we update the currentNumber based on the algorithm, re-assigning its value with its next value in the sequence.

if (currentNumber % 2 == 0)
    currentNumber = currentNumber / 2;
else
    currentNumber = currentNumber * 3 + 1;

Then we increment the number of steps, to indicate that we’ve just applied the algorithm:

stepCount++;

The while loop then continues until the currentNumber is equal to 1, after which we return the step count:

return stepCount;

Shortening

A ternary operator can be used instead of an if statement:

currentNumber = currentNumber % 2 == 0 ? currentNumber / 2 : currentNumber * 3 + 1;

Recursion

using System;

public static class CollatzConjecture
{
    public static int Steps(int number)
    {
        if (number <= 0)
            throw new ArgumentOutOfRangeException(nameof(number));

        return Steps(number, 0);
    }

    private static int Steps(int number, int stepCount)
    {
        if (number == 1)
            return stepCount;

        if (number % 2 == 0)
            return Steps(number / 2, stepCount + 1);

        return Steps(number * 3 + 1, stepCount + 1);
    }
}

The first step is to check the number parameter for validity:

if (number <= 0)
    throw new ArgumentOutOfRangeException(nameof(number));

The next step is to call the overload Steps() method and return its value.

return Steps(number, 0);

For someone new to the code, it might not be clear what the `0` argument in the `Steps(number, 0)` call represents.
You could introduce an appropriately named variable and use that as the argument:

```csharp
var stepCount = 0;
return Steps(number, stepCount);
```

This is already much better, but another option is to use a [named argument](https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/classes-and-structs/named-and-optional-arguments#named-arguments):

```csharp
return Steps(number, stepCount: 0);
```

Let’s examine the overload Steps() method, which looks like this:

private static int Steps(int number, int stepCount)
{
    if (number == 1)
        return stepCount;

    if (number % 2 == 0)
        return Steps(number / 2, stepCount + 1);

    return Steps(number * 3 + 1, stepCount + 1);
}

The first step is to check if the number parameter is equal to 1 If it is, we return the step count. This condition is often referred to the terminating condition, which is something that every recursive method must have (we’ll get to the recursive component next).

If the number is not 1, we need to apply the algorithm:

if (number % 2 == 0)
    return Steps(number / 2, stepCount + 1);

return Steps(number * 3 + 1, stepCount + 1);

We can see the algorithm being reflected here, but the interesting thing is that we’re calling the same method that we’re in but with different arguments. The two recursive calls represent the two options in the algorithm, and each applies the algorithm to the number to pass in the updated number of the first argument. The second argument is the step count, but incremented by one to indicate that we’ve applied the algorithm once.

The method call stack will look something like this:

Steps(4)
Steps(4, 0) // number = 4, stepCount = 0
Steps(2, 1) // number = 2, stepCount = 1
Steps(1, 2) // number = 1, stepCount = 2

Or in table format:

`number`	`stepCount`	Returned value
4	0	`Steps(number / 2, stepCount + 1)`
2	1	`Steps(number / 2, stepCount + 1)`
1	2	`stepCount`

You can see that the same method is called three times, with the third time no longer doing a recursive call but returning the step count as the terminating condition was reached.

Shortening

A ternary operator can be used instead of an if statement:

var nextNumer = number % 2 == 0 ? number / 2 : number * 3 + 1;
return Steps(nextNumer, stepCount + 1);

or just inline it:

return Steps(number % 2 == 0 ? number / 2 : number * 3 + 1, stepCount + 1);

Optional parameter

As an alternative to overloading the methods, as seen in the code snippets above, it is also possible to use an optional parameter to solve the problem with only a single method implementation.

This allows callers to use the method either with a single parameter (number) or both parameters, as used in the recursive method call. If only the number parameter is provided the stepCount parameter uses the defined default value.

public static int Steps(int number, int stepCount = 0)
{
    if (number <= 0)
        throw new ArgumentOutOfRangeException(nameof(number));

    if (number == 1)
        return stepCount;

    if (number % 2 == 0)
        return Steps(number / 2, stepCount + 1);

    return Steps(number * 3 + 1, stepCount + 1);
}

This version is more concise than the overloading version, but it comes with the drawback that the method API publicly exposes the stepCount parameter and callers might not know how to use this parameter correctly or may even provide invalid data, which then falsifies the result.

Sequence

using System;
using System.Collections.Generic;
using System.Linq;

public static class CollatzConjecture
{
    public static int Steps(int number)
    {
        if (number <= 0)
            throw new ArgumentOutOfRangeException(nameof(number));

        return Sequence(number).Count();
    }

    private static IEnumerable<int> Sequence(int number)
    {
        var currentNumber = number;

        while (currentNumber != 1)
        {
            if (currentNumber % 2 == 0)
                currentNumber = currentNumber / 2;
            else
                currentNumber = currentNumber * 3 + 1;

            yield return currentNumber;
        }
    }
}

The first step is to check the number parameter for validity:

if (number <= 0)
    throw new ArgumentOutOfRangeException(nameof(number));

In the second step, the Sequence() method is called with number as its argument. This method returns the sequence of numbers (IEnumerable<int>) that one gets by repeated application of the algorithm (excluding the number we start with). Then, we count the amount of numbers in that sequence to get the number of steps:

Number	Sequence	Count
2	1	1
4	2, 1	2
12	6, 3, 10, 5, 16, 8, 4, 2, 1	9

Let’s examine the Sequence() method more closely. As a reminder, this is what the method looks like:

private static IEnumerable<int> Sequence(int number)
{
    var currentNumber = number;

    while (currentNumber != 1)
    {
        if (currentNumber % 2 == 0)
            currentNumber = currentNumber / 2;
        else
            currentNumber = currentNumber * 3 + 1;

        yield return currentNumber;
    }
}

First, we start out with assigning the number parameter to a currentNumber variable, which we’ll use to keep track of where in the collatz conjecture sequence we currently are.

Re-assiging values to a parameter _is_ possible, but it is considered good practice to not do that.

Then a while loop starts by checking whether the current number is not equal to 1; if it is, the method terminates:

while (currentNumber != 1)

Within the loop, we update the currentNumber based on the algorithm, re-assigning its value with its next value in the sequence.

if (currentNumber % 2 == 0)
    currentNumber = currentNumber / 2;
else
    currentNumber = currentNumber * 3 + 1;

Finally, we use a yield statement to yield the current number.

yield return currentNumber;

When a yield statement is written, the compiler transforms the method into a state machine that is suspended after each yield statement. Note that even though we are yield indidivual elements, what is returned from a caller’s viewpoint is a sequence of elements.

Methods that use a yield statement are also lazy, which means that calling Sequence(number) by itself does not do anything. It is only when we call Count() on the sequence, that we’re forcing iteration over the elements in the sequence.

Using `yield` statement to generate a lazy sequence allows one to work with "infinite" sequences efficiently, as only the element to be returned (and the generated state machine) take up memory.

Shortening

A ternary operator can be used instead of an if statement:

currentNumber = currentNumber % 2 == 0 ? currentNumber / 2 : currentNumber * 3 + 1;

Source: Exercism csharp/collatz-conjecture