Реализация двойной факториальной хвостовой рекурсивной функции в C

Question

Я застрял, пытаясь реализовать следующую формулу в моем C коде:

N !! = N! / (N-1) !!

Предполагается, что код является хвосто-рекурсивной функцией, и хотя он работает и вычисления верны, я уверен, что это не функция хвоста + я действительно не могу сказать, что происходит во время стадии возврата.

Мой текущий код:

long long int Factorial(int n)    
{    
    if (n < 0)    
        return 0;

    if (n == 0 || n == 1)    
        return 1;

    return (n*Factorial(n - 1));    
}

int DoubleFactorialTail(int n, int fact)    
{
    if (n < 0)
    {
        return 0;
    }
    if (n == 0 || n == 1)
    {
        return fact;
    }
    else
    {
        long long int factorial = Factorial(n);
        return (factorial / DoubleFactorialTail(n - 1, fact));
    }
}

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

РЕДАКТИРОВАТЬ:

Первоначально я пытался реализовать следующее:

long long int DoubleFactorialTail(int n, int fact)

{
    if (n < 0)
    {
        return 1;
    }
    if (n == 0 || n == 1)
    {
        return fact;
    }
    else
    {
        return (DoubleFactorialTail(n - 2, fact*n));
    }
}

, и результат будет:

res = (Factorial(n)/DoubleFactorialTail(n-1, 1));

Дело в том, что нам сказали, что при n <0 функция должна вернуть 0 и сохранить его в res. но у этого уравнения будет 0 в знаменателе, если я решу продолжить и реализовать его таким образом. Поэтому я предполагаю, что мой главный вопрос: есть ли способ написать этот код методом хвостовой рекурсии, сохранив этот критерий без изменений? </p>

Answer 1

Я знаю, что двухфакторная хвостовая рекурсивная функция должна вызывать рекурсивную функцию в конце и ничего больше

Это правда, поэтому

return (n*Factorial(n - 1));

или

return (factorial / DoubleFactorialTail(n - 1, fact));

Не собирается работать.

Шаблон должен быть буквально

return CallToRecursive(args);

Причина в том, что рекурсивная оптимизация хвоста позволяет CallToRecursive(args); возврат к вызывающей стороне этой функции и не добавляет фрейм в стек вызовов.

Если вы добавляете код, который должен дополнительно обрабатывать возвращаемое значение, тогда ему нужен кадр в стеке вызовов для хранения возвращаемого значения и точки возврата, и это не TCO.

Чтобы подойти к этому, обычно передают незавершенную работу следующему вызову.

long long int FactorialTCO(int n, long long factSoFar)
{
    if (n < 0)
        return 0;

    if (n == 0 || n == 1)
        return factSoFar;

    return FactorialTCO(n - 1, n * factSoFar);
}

long long int Factorial(int n) {
     return FactorialTCO(n, 1);
}

Обратите внимание, что эта строка:

return FactorialTCO(n - 1, n * factSoFar);

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

Я оставляю преобразование double до вас или других.