tail recursion on double factorial equation in C

user_12460214 0
Viewed 548

I have a difficulty in implementing the tail recursive solution of the following problem:

There is another recursive relation for the double factorial, which also depends on the factorial, which is the above: (for n<20)

enter image description here

I have to implement a recursive relation of this equation- which I did as the above code that works:

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

Now I have to implement the same problem using a tail recursion. can someone show me how to do this because I cant figure it out. (no need to implement the factorial function also in a tail recursive way)

test cases:

  • 5!! = 15
  • 10!! = 3840
  • 18!! = 185,794,560
  • -10!! = 0
tail-recursion c
3 Answers

Here is a tail-recursive version of Factorial function:

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

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

factorial(5, 1); // 120

Here's a tail-recursive double factorial with a simpler logic:

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
user_111091190

If you expand your math a little bit you'll get that the factorial function result is iterating between the numerator and the denominator of the final result.

enter image description here

so this code will do that in 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)

And in 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);
}
user_25349800

Your definition of this double factorial function is incomplete: you need an initial value such as 0!! = 1. From the recurrence definition, it appears that p!! is the product of all numbers from 1 to p that have the same parity as p:

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

Computing the double factorial by computing the factorial and dividing by the result of the double factorial of the previous number will fail for numbers larger than 19 because of the limited range of integer types and the exponential growth of the factorial function. The double factorial grows quickly too, but its logarithm grows half as fast as that of the factorial function.

Here is an recursive function:

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

Here is a tail recursive implementation with a helper function:

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

The trick to convert the first function to a tail recursive one is instead of waiting for the result and multiplying then by n, pass an updated intermediary result to the recursive function. The multiplications are performed in the opposite order but will produce the same result (even modulo ULLONG_MAX+1).

user_45932670
Related