Problem 6: Double Factorial (100pts)

Problem

Let's write a function double_factorial, which takes a positive integer \(n\) and returns its double factorial.

Double factorial of a positive integer \(n\), denoted by \(n!!\), is defined as

\[n!!=\prod_{i=0}^{\lceil\frac{n}{2}\rceil-1}(n-2i)=n\times(n-2)\times(n-4)\times\cdots\]

This problem is an advanced version of this problem in Lab 01.

让我们编写一个函数 double_factorial，它接受一个正整数 \(n\) 并返回它的双阶乘。

正整数 \(n\) 的双阶乘，记作 \(n!!\)，定义为

\[n!!=\prod_{i=0}^{\lceil\frac{n}{2}\rceil-1}(n-2i)=n\times(n-2)\times(n-4)\times\cdots\]

这个问题是 Lab 01 中 这个问题 的进阶版本。

def double_factorial(n):
    """Compute the double factorial of n.

    >>> double_factorial(6)  # 6 * 4 * 2
    48
    >>> double_factorial(5)  # 5 * 3 * 1
    15
    >>> double_factorial(3)  # 3 * 1
    3
    >>> double_factorial(1)  # 1
    1
    """
    "*** YOUR CODE HERE ***"

Hints

• 你可能需要使用 while 循环。想想什么时候停止

• 用递归也很方便

Solutions

使用 while 循环解决这个问题。注意当 n < 1 时退出循环。

def double_factorial(n):
    result = 1
    # We start at n and step by -2 until we reach 1 or 2.
    i = n
    while i >= 1:
        result *= i
        i -= 2
    return result

---

使用递归解决：

def double_factorial(n):
    # Return 1 when n == 0 or 1
    if (n <= 1):
        return 1

    # Recursive step:
    return n * double_factorial(n - 2)