CODEWITHSUNDEEP
pythonmathfactorial
python learner
python learner

Reputation: 71

How do you a double factorial in python?

I've been stucked on this question for a really long time. I've managed to do a single recursive factorial.

def factorial(n):
     if n == 0:
         return 1
     else:
         return n * factorial(n-1)

Double factorial For an even integer n, the double factorial is the product of all even positive integers less than or equal to n. For an odd integer p, the double factorial is the product of all odd positive integers less than or equal to p.

If n is even, then n!! = n*(n - 2)*(n - 4)*(n - 6)* ... *4*2

If p is odd, then p!! = p*(p - 2)*(p - 4)*(p - 6)* ... *3*1

But I have no idea to do a double factorial. Any help?

Upvotes: 7

Views: 19510

Answers (11)

perm1ss10n
perm1ss10n

Reputation: 1

I ran into the same problem, I decided like this:

def double_factorial(N):
if N == 0: return 1
elif N == 1: return 1
elif N == 2: return 2
else:
    return N * double_factorial(N - 2)

Upvotes: 0

Kabie
Kabie

Reputation: 10673

from functools import reduce # only in Python 3

reduce(int.__mul__, range(n, 0, -2))

Upvotes: 19

Karol
Karol

Reputation: 1254

My version of the recursive solution, in one line:

dfact = lambda n: (n <= 0) or n * dfact(n-2)

However, it is also interesting to note that the double factorial can be expressed in terms of the "normal" factorial. For odd numbers,

n!! = (2*k)! / (2**k * k!)

where k = (n+1)/2. For even arguments n=2k, although this is not consistent with a generalization to complex arguments, the expression is simpler,

n!! = (2k)!! = 2*k * k!.

All this means that you can write code using the factorial function from the standard math library, which is always nice:

import math
fact = math.factorial
def dfact(n):
  if n % 2 == 1:
    k = (n+1)/2
    return fact(2*k) / (2**k * fact(k))
  else:
    return 2**k * fact(k)

Now, this code is obviously not very efficient for large n, but it is quite instructive. More importantly, since we are dealing with standard factorials now, it is a very good starting point for optimizations when dealing with really large numbers. You try to use logarithms or gamma functions to get approximate double factorials for large numbers.

Upvotes: 1

Xavier Guihot
Xavier Guihot

Reputation: 61666

Starting Python 3.8, we can use the prod function from the math module which calculates the product of all elements in an iterable, which in our case is range(n, 0, -2):

import math

math.prod(range(n, 0, -2))

Note that this also handles the case n = 0 in which case the result is 1.

Upvotes: 3

Eduardo Alberto Duarte Lacerda
Eduardo Alberto Duarte Lacerda

Reputation: 81

The problem here is that the double factorial is defined for negative real numbers (-1)!! = 1, (-3)!! = -1 (even negative integers (such -2, -4, ...) should have solution as +/- inf) so... something is smelling bad in all solutions for negative numbers. If one want to define the double factorial for al reals those solutions don't work. The solution is to define the double factorial using gamma function.

import scipy.special as sp
from numpy import pi

def dfact(x):
    n = (x + 1.)/2.
    return 2.**n * sp.gamma(n + 0.5)/(pi**(0.5))

It works! :D

Upvotes: 4

LoveAndCoding
LoveAndCoding

Reputation: 7947

def doublefactorial(n):
     if n <= 0:
         return 1
     else:
         return n * doublefactorial(n-2)

That should do it. Unless I'm misunderstanding

Upvotes: 0

kriss
kriss

Reputation: 24157

reduce(lambda x,y: y*x, range(n,1,-2))

Which is basically the same as the simple iterative version:

x = n
for y in range(n-2, 1, -2):
    x*=y

Obviously you can also do it recursively, but what's the point ? This kind of example implemented using recursivity are fine when using all recursive languages, but with imperative language it's always making simple tools like recursivity looking more complex than necessary, while recursivity can be a real simplifier when dealing with fundamentally recursive structures like trees.

Upvotes: 0

Navi
Navi

Reputation: 8736

I hope I understand it correctly, but will this work

 def factorial(n):
 if n == 0 or n == 1:
     return 1
 else:
     return n * factorial(n-2)

Upvotes: 0

Tauquir
Tauquir

Reputation: 6913

def double_fact(number):
    if number==0 or number==1:
        return 1
    else:
        return number*double_fact(number-2)

I think this should work for you.

Upvotes: 0

Lennart Regebro
Lennart Regebro

Reputation: 172229

def doublefactorial(n):
     if n in (0, 1):
         return 1
     else:
         return n * doublefactorial(n-2)

should do it.

Upvotes: 0

CanSpice
CanSpice

Reputation: 35788

Isn't that just the same as the factorial with a different ending condition and a different parameter to the recursion call?

def doublefactorial(n):
     if n <= 0:
         return 1
     else:
         return n * doublefactorial(n-2)

If n is even, then it will halt when n == 0. If n is odd, then it will halt when n == -1.

Upvotes: 5

Related Questions