如何在Python中计算双阶乘？

Question

我在这个问题上卡了很长时间。我已经成功地完成了一个递归阶乘。

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

双阶乘

对于一个偶数n，其双阶乘是所有小于等于n的正偶数的积。对于一个奇数p，其双阶乘是所有小于等于p的正奇数的积。

如果n是偶数，则 n!! = n*(n - 2)*(n - 4)*(n - 6)* ... *4*2

如果p是奇数，则 p!! = p*(p - 2)*(p - 4)*(p - 6)* ... *3*1

但我不知道如何计算双阶乘。有什么帮助吗？

- python learner

---

看一下这两者之间的变化：n-1 变成了 n-2，而最终数字（基本情况）从 0 变成了 2 或 1 中的一个。 - moinudin

Answer 1

from functools import reduce # only in Python 3

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

- Kabie

---

等等，这实际上会被点赞吗？至少使用operator.mul（相对更清晰，因为您不需要输入下划线，并且是“类型不可知的”）。如果我要避免堆栈溢出，我个人更喜欢显式迭代版本，正如下面所提到的，那并不是大多数阶乘分配的重点。 - user395760

任何阶乘函数的重点都是教授人们递归，而不是实际效率。你会发现xrange甚至更有效率。 ;) - Lennart Regebro

@delnan：由于range只产生int，因此使用int.__mul__是可以的（而且不必进行另一个导入）。@Lennart Regebro：没错。但是我在Python 3中编写了这段代码。至于递归的使用，您不认为reduce可以被视为递归函数吗？理解它可能会有所帮助。 - Kabie

reduce(long.__mul__,range(n,0,-2),1L) 避免了当乘积过大时出现问题。 - John La Rooy

这被认为是混淆的Python代码？哇，对我来说看起来很正常，这只是一个标准的折叠函数，就像我在Haskell或Lisp中使用的一样。 - alternative

Answer 2

这不就是阶乘，只是结束条件和递归调用的参数不同吗？

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

如果n是偶数，则当n == 0时它将停止。如果n是奇数，则当n == -1时它将停止。

- CanSpice

---

在递归调用中，您需要调用doublefactorial。我也犯了同样的错误。 - LoveAndCoding

你可以在1处停止而不是-1。我知道，这只是微小的改进，但仍然有用。 :) - Lennart Regebro

Answer 3

问题在于双阶乘被定义在负实数上，(-1)!! = 1, (-3)!! = -1（甚至像-2、-4等偶数负整数应该有+/- inf的解）因此...所有针对负数的解决方法都有点不对劲。如果我们想要将双阶乘定义到所有实数上，这些解决方法就行不通了。解决方案是使用伽玛函数来定义双阶乘。

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

它可以工作了！:D

- Eduardo Alberto Duarte Lacerda

---

这只适用于奇数x，对吗？ - mikuszefski

Answer 4

从Python 3.8开始，我们可以使用math模块中的prod函数计算可迭代对象中所有元素的积，而在本例中，这个可迭代对象是range(n, 0, -2)：

import math

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

请注意，这也处理了n = 0的情况，此时结果为1。

- Xavier Guihot

Answer 5

以下是我的递归解决方案，只有一行：

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

然而，有趣的是双阶乘可以用“普通”阶乘表示。对于奇数，n!! = (2*k)! / (2**k * k!)，其中k = (n+1)/2。对于偶数参数n=2k，虽然这不符合到复数参数的推广，但表达式更简单，n!! = (2k)!! = 2*k * k!。这意味着您可以使用标准数学库中的阶乘函数编写代码，这总是很好的：

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)

现在，对于大的n值，这段代码显然不是很高效，但它相当具有教育意义。更重要的是，由于我们现在正在处理标准阶乘，因此在处理非常大的数字时进行优化的起点非常好。您可以尝试使用对数或伽马函数来获取大数的近似双阶乘。

- Karol

Answer 6

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

应该就可以了，除非我误解了什么

- LoveAndCoding

---

дёәд»Җд№ҲеҪ“n == 0ж—¶дҪ иҝ”еӣһ2пјҹеә”иҜҘиҝ”еӣһ1пјҢеҸӘйңҖдҪҝз”Ёif n <= 1: return 1пјҢдҪҶе®һйҷ…дёҠеә”иҜҘжҳҜif n < 0: еӨ§еЈ°е°–еҸ« if n in (0, 1): return 1гҖӮ - wich

Answer 7

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

应该这样做。

- Lennart Regebro

Answer 8

我希望我理解得正确，但这会起作用吗？

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

- Navi

---

不太对。你需要调整基本情况，否则它不会在奇数上终止。 - user395760

你需要在小于0的地方停止，否则奇数值将进入无限循环（或最终导致堆栈溢出）。 - LoveAndCoding

Answer 9

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

我认为这对你应该有效。

- Tauquir

Answer 10

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

这基本上与简单的迭代版本相同：

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

显然，您也可以使用递归来实现它，但这有什么意义呢？这种使用递归实现的示例在使用所有递归语言时都很好，但是对于命令式语言而言，使用递归总是使像递归这样的简单工具看起来比必要的更加复杂，而当处理基本上是递归的结构（如树）时，递归可以是一个真正的简化器。

- kriss