用于计算阶乘的递归函数对于较大的数字不能正常工作

Question

我正在学习数据结构课程，并试图在Julia中复制相同的课程。

我在Julia中使用下面的代码-

function factorial(n)
if n <= 1
return 1
else
return n*factorial(n-1)
end
end

对于小于或等于20的数字，它工作得很好，但对于21或更大的数字，我得到的是负值。同样的逻辑在Python中运行良好，下面是代码-

def factorial(n):
assert n >= 0 and int(n) == n, 'The number must be positive integer only'
if n <= 1:
return 1
else:
return n*factorial(n-1)

你能帮我了解问题是什么吗?

Answer 1

正如评论中提到的，你可以传入一个BigInt作为输入来计算更大的数字。

为了保持代码类型的稳定，返回one(n)而不是1。这将确保返回作为输入发送的任何类型，从而保持代码类型的稳定。

julia> function factorial(n)
if n <= 1
return one(n)
else
return factorial(n - 1) * n
end
end
factorial (generic function with 1 method)

输出

julia> typeof(factorial(10))
Int64
julia> typeof(factorial(BigInt(10)))
BigInt
julia> typeof(factorial(big"100"))
BigInt
julia> factorial(big"100")
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

选择一行程序

还可以使用Julia的三元操作符将上面的函数写成一行代码。

factorial(n) = n <= 1 ? one(n) : factorial(n-1) * n

Answer 2

如下所示:

在Julia中，超过给定类型的最大可表示值将导致环绕行为

和Int64类型(在64位机器上默认用于存储整数)的范围是:

julia> typemin(Int64)
-9223372036854775808
julia> typemax(Int64)
9223372036854775807

使用BigInt实现任意精度整数。可以使用big函数将任意整数转换为BigInt。这种方法的缺点是函数会变慢:

function factorial(n)
if n <= 1
return big(1)
else
return big(n) * factorial(n-1)
end
end

现在你有:

julia> factorial(21)
51090942171709440000
julia> factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

编辑

显示OP代码类型不稳定的示例:

julia> using Test
julia> function factorial(n)
if n <= 1
return 1
else
return n*factorial(n-1)
end
end
factorial (generic function with 1 method)
julia> @inferred factorial(big"21")
ERROR: return type BigInt does not match inferred return type Union{Int64, BigInt}