我的Python阶乘代码有什么问题？

Question

我有以下Python代码用于计算数字的阶乘，但我无法理解为什么我的答案是1。请问有谁能纠正我的代码？我想要不使用递归来计算阶乘。

def factorial (n):
        result =1 
        num = n
        while n<1:
            result = result * num
            num = num -1
        return result

    factorial(5)
    1

- dangerous

---

循环条件取决于 n，但是在循环中你只改变了 result 和 num。这个循环将会运行 0 次或无限次。 - LeeNeverGup

正如Frerich和PM 2Ring所详细说明的那样，math.factorial要快得多。 - AncientSwordRage

@Pureferret 我认为我们在这里必须假设，OP的目标不仅仅是他有一些数字，想知道它们的阶乘是多少。 - jwg

Answer 1

while n < 1:

应该改为

while num > 1:

- Simon Gibbons

Answer 2

其他人已经指出了您代码中的问题，但是我想指出一个事实，即阶乘函数确实适合更多的函数式（如：函数式编程）解决方案；这避免了完全使用while循环来获取条件的问题，因为您根本没有任何循环。关键在于，n的阶乘是1..n的乘积，而乘积可以非常容易地使用Python的reduce函数定义。为了避免失去性能，这是我在Python 2.7解释器中给出的您（修复后）的代码：

python -m timeit -s "import original" "original.factorial(10)"
1000000 loops, best of 3: 1.22 usec per loop

一种更为简洁的声明式方法是使用一行代码：

def factorial(n):
    return reduce(lambda x,y: x*y, range(1, n+1))

然而，它更慢了：

python -m timeit -s "import func1" "func1.factorial(10)"
1000000 loops, best of 3: 1.98 usec per loop

然而，这个问题可以通过使用xrange代替range，以及使用operator.mul代替自定义的lambda函数来解决:

import operator

def factorial(n):
    return reduce(operator.mul, xrange(1, n+1))

对我来说，这比原始代码还要快：

python -m timeit -s "import func2" "func2.factorial(10)"
1000000 loops, best of 3: 1.14 usec per loop

个人而言，我会将reduce调用分离出来，以使代码更加清晰易懂（牺牲了一点点性能）：

import operator

def product(it):
    return reduce(operator.mul, it)

def factorial(n):
    return product(xrange(1, n+1))

我喜欢这个版本是因为它快速明了：阶乘被定义为范围[1..n+1[（即排除n+1）的积。如果你尝试计算更大数的阶乘，性能差异会更加明显：

python -m timeit -s "import original" "original.factorial(30)"
100000 loops, best of 3: 5.25 usec per loop

对比。

python -m timeit -s "import func3" "func3.factorial(30)"
100000 loops, best of 3: 3.96 usec per loop

- Frerich Raabe

---

这个回答如何回答这个问题？ - AncientSwordRage

@Pureferret：它并没有回答问题（问题已经被回答了），它通过展示替代实现方式来扩展已有的答案，这些实现方式本身就能避免问题的出现（因为不需要显式的“for”循环）。 - Frerich Raabe

@Pureferret 一个注释并不能提供足够的空间（更不用说可读性）来容纳我所写的内容。 - Frerich Raabe

@Pureferret提到的是关于如何减少外部链接对Stack Overflow的负面影响的问题，而正如那个回答所引用的，“SO的主要目标之一是提供一个全面的问答库（而不仅仅是一个问答论坛）”。如果被采纳的答案作者能够在他的文本中加入我的内容，我会很高兴，但只要这种情况不存在，添加另一个退步的答案是一个公平的妥协。如果这能让你满意，我也可以添加“将n<1改为num>1。”的建议。 - Frerich Raabe

@FrerichRaabe - 很好的解释。我无法更改已接受的答案，因为这并没有回答我的问题。但是你的解释向我介绍了许多新概念。我已经为你的解决方案点赞。 - dangerous

Answer 3

while 5 < 1 这句话始终为false，因此返回result = 1是错误的。

- user1907906

---

搞定了！！这是个愚蠢的错误。我是编程新手。 - dangerous

我应该学习递归吗？我对递归的概念感到非常困惑。或者在Python中使用循环是否足够？ - dangerous

当然，你应该学习递归的概念。哪种方法最好取决于具体情况。 - user1907906

Answer 4

让我们看看：

1. 当你调用函数时，你将 n=5 设定为参数。
2. 你告诉 Python 当 n < 1 时执行某些操作。
3. n 已经比 1 大了，所以不会执行 while 循环里的代码。
4. 你的代码返回 result，在定义的第一行设定为 1。

- Luis González

Answer 5

正如Simon Gibbons所解释的那样，您的代码中有

while n < 1:

而不是

while num > 1:

因此，您使用“小于”而不是“大于”，因此您的while语句中的测试将立即失败。但是，如果您将其更改为while n > 1:，它将永远循环，因为您从未在while循环内更改n的值。

Haresh Shyara发布了您的代码的已更正版本，如下所示：

def factorial(n):
    result = 1
    while n > 1:
        result = result * n
        n = n - 1
    return result

请注意，此代码不会复制n到num，而是直接使用n。这不会影响您调用函数的参数，因为：

1. Python整数是不可变的；
2. n = n - 1实际上创建了一个名为n的新本地对象。

---

我受到Frerich Raabe答案的启发，写了一个程序以更系统化的方式对这里提供的各种解决方案进行计时。我还包括了math.factorial()和一个简单的基于for循环的函数。

我稍微优化了调用operator.mul的函数，通过定义mul = operator.mul，但我必须向使用reduce()的那些函数提供一个初始参数1，以便它们不会在factorial(0)上失败（应返回1）。

我大致按速度从快到慢地排列了这些函数。

我刚刚增强了这个程序，使其更容易运行多个测试并添加新的要测试的函数。此外，在运行计时测试之前，它现在打印每个函数的简要描述，使用函数的docstring。并且在运行计时测试之前，它会验证每个函数计算正确的值。

#!/usr/bin/env python

''' Test and time various implementations of the factorial function

    From https://dev59.com/aIfca4cB1Zd3GeqPnsyW

    Written by PM 2Ring 2015.02.13
'''

import operator
import math
from timeit import Timer

factorial0 = math.factorial

def factorial0a(n):
    ''' call math.factorial '''
    return math.factorial(n)

def factorial1(n):
    ''' for loop'''
    p = 1
    for i in xrange(2, n+1):
        p *= i
    return p

mul = operator.mul

def product(it):
    return reduce(mul, it, 1)

def factorial2(n):
    ''' reduce with op.mul '''
    return reduce(mul, xrange(1, n+1), 1)

def factorial3(n):
    ''' call product() '''
    return product(xrange(1, n+1))    

def factorial4(n):
    ''' while loop '''
    result = 1
    while n > 1:
        result = result * n
        n = n - 1
    return result

def factorial4a(n):
    ''' while loop with assignment operators '''
    result = 1
    while n > 1:
        result *= n
        n -= 1
    return result

def factorial5(n):
    ''' recursive '''
    if n <= 1:
        return 1;
    else:
        return n*factorial5(n-1)

def factorial6(n):
    ''' reduce with lambda '''
    return reduce(lambda res, val: res*val, xrange(n, 0, -1), 1)

funcs = (
    factorial0,
    factorial0a,
    factorial1,
    factorial2,
    factorial3,
    factorial4,
    factorial4a,
    factorial5,
    factorial6,
)

def verify(n):
    ''' Check that each function calculates the same result as math.factorial '''
    r = xrange(n)
    fac = [factorial0(i) for i in r]
    rc = True
    for func in funcs[1:]:
        for i in r:
            v = func(i)
            if v != fac[i]:
                print 'Error: %s(%d) returns %d instead of %d' % (func.func_name, i, v, fac[i])
                rc = False
    return rc

def time_test(arg=10, loops=100000, reps=3):
    ''' Print timing stats for all the factorial functions '''
    print 'Arg = %d, Loops = %d, Repetitions = %d' % (arg, loops, reps)

    for func in funcs:
        #Get function name and docstring
        try:
            fname = func.func_name
            fdoc = func.__doc__
        except AttributeError:
            #Math.factorial has no name, and we can't modify its docstring
            fname = 'factorial0'
            fdoc = ' math.factorial itself '

        print '\n%s:%s' % (fname, fdoc)
        t = Timer('%s(%d)' % (fname, arg), 'from __main__ import %s' % fname)
        r = t.repeat(reps, loops)
        r.sort()
        print r
    print '\n'

def main():
    if not verify(100): exit(1)
    time_test(arg=5, loops=500000, reps=4)
    time_test(arg=10, loops=200000, reps=4)
    time_test(arg=50, loops=100000, reps=4)

if __name__ == '__main__':
    main()

输出

Arg = 5, Loops = 500000, Repetitions = 4

factorial0: math.factorial itself 
[0.30838108062744141, 0.3119349479675293, 0.31210899353027344, 0.32166290283203125]

factorial0a: call math.factorial 
[0.62141299247741699, 0.62747406959533691, 0.63309717178344727, 0.66500306129455566]

factorial1: for loop
[1.4656128883361816, 1.476855993270874, 1.4897668361663818, 1.5052030086517334]

factorial2: reduce with op.mul 
[1.5841941833496094, 1.5868480205535889, 1.6007061004638672, 1.6253509521484375]

factorial3: call product() 
[1.8745129108428955, 1.8750350475311279, 1.8822829723358154, 1.9097139835357666]

factorial4: while loop 
[1.1264691352844238, 1.1348199844360352, 1.1348659992218018, 1.178135871887207]

factorial4a: while loop with assignment operators 
[1.1867551803588867, 1.1881229877471924, 1.1893219947814941, 1.2020411491394043]

factorial5: recursive 
[1.9756920337677002, 1.9862890243530273, 1.9910380840301514, 2.0284240245819092]

factorial6: reduce with lambda 
[2.8342490196228027, 2.8369259834289551, 2.8390510082244873, 2.8969988822937012]


Arg = 10, Loops = 200000, Repetitions = 4

factorial0: math.factorial itself 
[0.24756813049316406, 0.24919605255126953, 0.26395106315612793, 0.28582406044006348]

factorial0a: call math.factorial 
[0.3732609748840332, 0.37482404708862305, 0.37592387199401855, 0.38288402557373047]

factorial1: for loop
[0.88677501678466797, 0.89632201194763184, 0.89948821067810059, 0.90272784233093262]

factorial2: reduce with op.mul 
[0.89040708541870117, 0.89259791374206543, 0.89863204956054688, 0.90652203559875488]

factorial3: call product() 
[1.0093960762023926, 1.031667947769165, 1.2325050830841064, 1.7492170333862305]

factorial4: while loop 
[0.93423891067504883, 0.93978404998779297, 0.94000387191772461, 0.95153117179870605]

factorial4a: while loop with assignment operators 
[0.97296595573425293, 0.97462797164916992, 0.98288702964782715, 1.0095341205596924]

factorial5: recursive 
[1.6726200580596924, 1.6786048412322998, 1.691572904586792, 1.6946439743041992]

factorial6: reduce with lambda 
[1.8484599590301514, 1.8502249717712402, 1.8615908622741699, 1.9228360652923584]


Arg = 50, Loops = 100000, Repetitions = 4

factorial0: math.factorial itself 
[1.6450450420379639, 1.6641650199890137, 1.6790158748626709, 1.7192811965942383]

factorial0a: call math.factorial 
[1.7563199996948242, 2.0039281845092773, 2.1530590057373047, 2.3621060848236084]

factorial1: for loop
[2.7895750999450684, 2.8117640018463135, 2.8381040096282959, 3.0019519329071045]

factorial2: reduce with op.mul 
[2.4697721004486084, 2.4750289916992188, 2.4813871383666992, 2.5051541328430176]

factorial3: call product() 
[2.4983038902282715, 2.4994339942932129, 2.5271379947662354, 2.5356400012969971]

factorial4: while loop 
[3.6446011066436768, 3.650169849395752, 3.6579680442810059, 3.7304909229278564]

factorial4a: while loop with assignment operators 
[3.7421870231628418, 3.7477319240570068, 3.7655398845672607, 3.7749569416046143]

factorial5: recursive 
[5.523845911026001, 5.5555410385131836, 5.5760359764099121, 6.2132260799407959]

factorial6: reduce with lambda 
[4.9984982013702393, 5.0106558799743652, 5.0363597869873047, 5.0808289051055908]

与所有timeit结果一样，每个列表中最快的条目是重要的，较慢的条目应被忽略。

来自timeit文档（由Ffisegydd提供）：

“...最低值给出了您的机器运行给定代码片段的下限；结果向量中的较高值通常不是由Python速度的可变性引起的，而是由其他进程干扰您的计时精度。因此，结果的min()可能是您唯一感兴趣的数字...”

- PM 2Ring

---

我对reduce在这个上下文中的确切应用感到困惑。reduce接受一个函数并将其应用于每个可迭代对象。因此，这里的lambda函数将两个数字相乘。那么，如果我想计算5的阶乘，该如何使用这段代码实现呢？ - dangerous

@dangerous：我的原始for循环解决方案已经在我的答案中了：它是factorial1()。我不会将其作为单独的答案发布，因为在所有Stack Exchange网站上，一个人对一个问题发布多个答案是极其不鼓励的。但请随意给这个答案点赞。 :) 但是，如果你说的是等同于volcano代码的for循环，请参见他的答案。 - PM 2Ring

我认为速度优化不是这里的重要目标。 - jwg

@jwg：当然，对于OP的问题，主要答案是解释他们的逻辑有什么问题。然而，Stack Overflow不仅仅是为了回答OP的具体问题，SO的答案也应该对未来的读者有用。编写阶乘函数是一个常见的初学者作业，将多种算法放在一个地方，让人们可以进行比较和对比，这是很好的。 - PM 2Ring

如果有人想要速度，他们不应该使用自己的阶乘函数：他们应该使用内置的 math.factorial，或者是第三方的 gmpy 或 mpmath 模块。而且，如果他们真的需要速度，他们不应该使用标准的 Python，而应该使用可以编译成机器代码的东西。 - PM 2Ring

Answer 6

def factorial(n):
    result = 1
    while n > 1:
        result = result * n
        n = n - 1
    return result

print factorial(5)
120

- Haresh Shyara

---

这种类型的回答并不是很有帮助。你只是提供了一个固定的代码片段。请解释原始片段的问题在哪里，以及为什么你的版本可以工作。即使被接受的答案只有一小部分代码，但它更好，因为它以更清晰的方式解释了问题。 - Chris

当 n < 1 时，原始代码片段是错误的，因为 n = 5，所以 (5 < 1) 是假的，因此您的控制不会执行主体部分，返回结果=1。第二个问题是您在 while 循环中使用变量 n 并减少 num 变量。 - Haresh Shyara

Answer 7

你的代码不会进入 while 循环本身。将其从 n<1 改为 n>1。例如，查找 5 的阶乘，n<1 将被视为 5<1，这是错误的。

- kvivek

Answer 8

试试这个，更简洁：

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

这是一种递归解决问题的方法。

- Luis González

---

递归方式为什么更简洁？ - user1907906

也许“cleaner”这个词不太准确，但我认为这种写法更好。你可以用更少的代码行数，并且使用常见或自然的方式来理解阶乘运算：N！= N *（N-1）！，除非N = 1，然后N！= 1。这真的是个人意见。 - Luis González

Python中的递归不是最优化的，并且它有一个递归深度的限制（尽管这个限制可以被修改）。一些问题最好使用递归来解决（例如树处理），但一般情况下，如果您可以轻松用迭代算法解决您的问题，那么最好避免使用递归。 - PM 2Ring

即使堆栈是无限的，使用堆栈过多仍然会有惩罚 - 对于那些可以通过迭代轻松解决的问题，没有真正的理由使用它。@PM2Ring - volcano

@volcano：确实，大量的堆栈使用不仅会增加程序的内存使用量，还会使其变慢。正如我刚刚发布的时间表所示，递归阶乘相对较慢。 - PM 2Ring

Answer 9

说到简短的Pythonic代码

def factorial(n):
    return reduce(lambda res, val: res*val, xrange(n, 0, -1), 1)

---

对于那些不理解 volcano 代码如何工作的人，这里是一个接近的近似值：

''' Equivalent code by PM 2Ring '''

def f(res, val):
    return res * val

def factorial(n):
    res = 1
    for val in xrange(n, 0, -1):
        res = f(res, val)
    return res

- volcano

---

这看起来与提问者的代码完全不同，那么这有什么帮助呢？ - AncientSwordRage

@Pureferret，下投票的理由很蠢 - 但你随意。只是出于好奇 - 你是否对在此线程中提供替代解决方案的所有答案进行了投票？ - volcano

@volcano- 你的解决方案看起来有些不同。你能解释一下函数 reduce(lambda res, val: resval, xrange(n, 0, -1), 1) 是如何工作的吗？我知道 lambda res,val : resval 可以将两个数字相乘。但是我无法理解 reduce(function, xrange(n,0,-1),1) 的逻辑。你能详细说明一下吗？ - dangerous

实际上，反向范围是没有意义的 - 我在编写时没有想清楚。初始值也是多余的 - 我不经常使用 reduce，所以最初忽略了它。 - volcano

初始值不是多余的：考虑一下 factorial(0) 会发生什么。 - PM 2Ring