Язык Си: рекурсия и гипотеза Коллатца

Продолжаем проходить курс Computer Science CS50 и язык C. Изучаем рекурсию на примере гипотезы Коллатца — интересной (и простой для понимания) математической проблемы, которая все еще не решена учеными.

Гипотеза Коллатца:

1. Возьмем любое положительное целое число
2. Если оно чётное, то поделим его на 2
3. Если нечётное, то  умножаем на 3 и прибавляем 1 (получаем n * 3 + 1).
4. Далее полученное число снова оцениваем — четное оно или нет и снова  выполняем те же самые действия, до тех пор, пока не получим 1.

Итого, суть гипотезы Коллатца в том, что абсолютно любое число при применении к нему этих двух простых операций рано или поздно превратится в 1.

Если посмотреть на эту проблему в традиционном ключе и попробовать решить через цикл без применения рекурсии, получим такой код (решение Игроглаза):

#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++;
}

Теперь попробуем написать код с рекурсией. У нас один базовый случай: если n равно 1, то пора выйти из рекурсии. И у нас есть два рекурсивных случая:

1. если n четное, мы делаем один рекурсивный случай, деля n на 2.
2. если n нечетное, мы делаем другой рекурсивный случай для 3 раз n плюс 1.

Итак, цель — написать рекурсивную функцию Коллатца, где мы передаем значение n, и функция вычисляет, сколько шагов потребуется, чтобы добраться до 1. Если n равно 1, то требуется 0 шагов. В противном случае будем делать один шаг плюс столько же шагов, сколько потребуется либо для n, деленного на 2, если n четное, либо для 3*n плюс 1, если n нечетное.

Вот несколько тестовых значений, чтобы проверить различные числа Коллатца, а также увидеть шаги, которые необходимо пройти, чтобы прийти к 1.

Итак, попробуем рекурсивно определить число Коллатца для n; чтобы наши функция вычисляла, сколько шагов требуется для того, чтобы подойти к 1.

Рекурсия — вариант Штукенции (как посчитать количество шагов для n, если к примеру n=27; можно подставить свое любое значение в скобках):

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

Штукенция отлично справилась 🙂 От меня она услышала подсказку насчет глобальной переменной. Я тоже от нее кое-чему научился. Изначально я написал корявую версию рекурсии, которая корректно не выходила из вложенных функций — ошибочная рекурсия от Игроглаза:

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

При этом этот код выдает правильный результат. После решения задачи мы со Штукенцией поменялись стульями — чтобы она посмотрела мой код, а я ее. Краем глаза я увидел, что она выходит из рекурсивных случаев через return и удивился. Но еще до обмена стульями, я удивился, что у меня у меня очень странный возврат steps if (n == 1) return steps;  — выдает какие-то пятизначные значения, хотя по дебагеру количество шагов — корректно. Поэтому я и поменял steps на 0 и вывел чисто steps в main в первой версии программы 😉

Начал дебажить и в процессе понял, что из рекурсивных функция я не выхожу, а оставляю их висеть… Вспомнил про return у Штукенции (эх, жаль я его подсмотрел случайно, а не сам додумался). В итоге, вот корректная версия рекурсии от Игроглаза:

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

Вот уж не думал, что гуманитарии справятся с такими вещами 🙂 Тем не менее, мы со Штукенцией два что ни на есть гуманитария. И все получается. Так что и у вас все будет отлично!