хвостовая рекурсия по двойному факториальному уравнению в C

Question

Мне трудно реализовать хвостовое рекурсивное решение следующей задачи:

Существует еще одно рекурсивное отношение для двойного факториала, которое также зависит от факториала, как указано выше: (для n < 20)

Я должен реализовать рекурсивное соотношение этого уравнения - , которое я сделал как приведенный выше код, который работает :

long long factorial(int n) {
    if (n < 0)
        return 0;
    if (n < 1)
        return 1;

     return n * factorial(n - 1);
}

long long doublefactorial(int n) {
    if (n < 0)
        return 0;
    if (n < 2)
        return 1;
    return factorial(n) / doublefactorial(n - 1);
}

Теперь я должен реализовать ту же проблему, используя хвостовую рекурсию . может кто-нибудь показать мне, как это сделать, потому что я не могу понять это. (нет необходимости реализовывать функцию факториала также хвостовым рекурсивным способом)

контрольные примеры:

• 5 !! = 15
• 10 !! = 3840
• 18 !! = 185 794 560
• -10 !! = 0

Answer 1

Если вы немного расширите свою математику, вы получите, что результат факториальной функции повторяется между числителем и знаменателем конечного результата.

, поэтому этот код сделает это в Python

def _factorial(n, m):
    if n < 0:
        return 0
    elif n == 0:
        return 1.0 * m
    return _factorial(n - 1, n * m)

def factorial(n):
    return _factorial(n, 1)

def _doublefactorial(n, m, is_even):
    if n < 0:
        return 0
    elif n < 2:
        return 1.0 * m

    if is_even:
        m *= factorial(n)
    else:
        m /= factorial(n)

    return _doublefactorial(n - 1, m, (not is_even))

def doublefactorial(n):
    return _doublefactorial(n, 1, True)

И в C:

unsigned int _factorial(const unsigned int n, const unsigned int m) {
    if (n < 0) {
        return 0;
    } else if (n == 0) {
        return m;
    }
    return _factorial(n - 1, n * m);
}

unsigned int factorial(const unsigned int n) {
    return _factorial(n, 1);
}

double _doublefactorial(const unsigned int n, const double m, const char is_even) {
    double value = m;

    if (n < 0) {
        return 0;
    } else if (n < 2) {
        return m;
    }

    if (is_even) {
        value *= factorial(n);
    } else {
        value /= factorial(n);
    }

    return _doublefactorial(n - 1, value, !is_even);
}

double doublefactorial(const unsigned int n) {
    return _doublefactorial(n, 1, 1);
}

Answer 2

Вот хвост-рекурсивная версия факториальной функции:

long factorial(int n, int factor)
{
    if (n == 0)
        return factor;

    return factorial(n-1, factor * n);
}

factorial(5, 1); // 120

Вот хвост-рекурсивный двойной факториал с более простой логикой c:

long doublefactorial(int n, int factor)
{
    if (n < 0)
        return 0;
    if (n < 2)
        return factor;

    return doublefactorial(n-2, factor * n);
}

printf("%d ", doublefactorial(5,1)); // 15
printf("%d ", doublefactorial(10,1)); // 3840
printf("%d ", doublefactorial(18,1)); // 185794560 

Answer 3

Ваше определение этой двухфакторной функции неполное: вам нужно начальное значение, такое как 0 !! = 1 . Из определения повторения следует, что p !! является произведением всех чисел от 1 до p , имеющих одинаковую четность с p :

• 5 !! = 1 * 3 * 5 = 15
• 6 !! = 2 * 4 * 6 = 48
• 10 !! = 2 * 4 * 6 * 8 * 10 = 3840

Вычисление двойного факториала путем вычисления факториала и деления на результат двойного факториала предыдущего числа завершится ошибкой для чисел, больших 19, потому что ограниченного диапазона целочисленных типов и экспоненциального роста факториальной функции. Двойной факториал тоже быстро растет, но его логарифм увеличивается вдвое быстрее, чем у факториальной функции.

Вот рекурсивная функция:

unsigned long long doublefactorial(int n) {
    if (n < 0)
        return 0;
    if (n < 2)
        return 1;
    return n * doublefactorial(n - 2);
}

Вот хвостовая рекурсивная реализация с вспомогательная функция:

unsigned long long doublefactorial_helper(int n, unsigned long long res) {
    if (n < 2)
        return res;
    return doublefactorial(n - 2, res * n);
}

unsigned long long doublefactorial(int n) {
    return doublefactorial_helper(n, n >= 0);
}

Хитрость для преобразования первой функции в хвостовую рекурсивную заключается в том, чтобы вместо ожидания результата и умножения на n передать обновленный промежуточный результат в рекурсивную функцию. Умножения выполняются в обратном порядке, но дают тот же результат (даже по модулю ULLONG_MAX+1).