在Julia中理解没有基本情况的递归

Question

这段代码来自于Julia中有关有理数的实现部分：

# Rational.jl
# ...
Rational{T<:Integer}(n::T, d::T) = Rational{T}(n,d)
Rational(n::Integer, d::Integer) = Rational(promote(n,d)...)
Rational(n::Integer) = Rational(n,one(n))

//(x::Rational, y::Integer) = x.num // (x.den*y) <--- HERE!

# ...

看到//函数是如何实现并与中缀符号一起使用的吗? 那这实际上是如何返回一个值的呢？

当我看到这段代码时，我按照以下方式解释它：

1. 使用Rational和Integer调用//函数。
2. 但随后它会不带其他参数地进行递归调用。

#2 是真正让我感到困惑的地方。数据结构内部的递归是在哪里结束的？如果不断评估无内容，//如何返回一个值呢？

请帮我理解这个问题。

- dopatraman

Answer 1

这项工作的原因是由于Julia语言最基本的特性之一：多重派发。在Julia中，函数可以有许多方法，这些方法适用于各种参数类型的组合，当您调用一个函数时，Julia会调用与您调用它时使用的所有参数类型匹配的最具体的方法。您发布的方法定义中的// 调用是将有理数-整数//定义为整数-整数//的一部分——因此它实际上不是递归，因为该方法没有调用自身，而是调用了同一个“通用函数”中的另一种方法。

为了理解多重派发在这种情况下如何工作，让我们考虑表达式(3//4)//6的求值。我们将使用@which宏来查看每个函数调用调用的方法。

julia> @which (3//4)//6
//(x::Rational{T<:Integer}, y::Integer) at rational.jl:25

由于3//4是一个Rational{Int} <: Rational，而6是一个Int <: Integer，且没有适用于此情况的更加具体的方法，因此调用了这个方法：

//(x::Rational, y::Integer) = x.num // (x.den*y)

这种方法的当前版本实际上比您发布的稍微复杂一些，因为它已经被修改以检查是否存在整数溢出 - 但本质上是相同的，而且更容易理解旧的、更简单的版本，所以我将使用那个版本。让我们将x和y分别赋值为参数，并看一下定义调用了哪个方法：

julia> x, y = (3//4), 6
(3//4,6)

julia> x.num
3

julia> x.den*y
24

julia> x.num // (x.den*y)
1//8

julia> @which x.num // (x.den*y)
//(n::Integer, d::Integer) at rational.jl:22

你可以看到，这个表达式调用的不是同一个方法，而是调用了另一个方法：

//(n::Integer,  d::Integer) = Rational(n,d)

这种方法只是调用了 Rational 构造函数，该函数将 n 和 d 的比率化为最简分数，并创建了一个 Rational 数字对象。

在 Julia 中，通常会通过定义同一函数的另一个方法来定义该函数的一个方法。例如，这就是参数默认值的工作方式。考虑下面的定义：

julia> f(x, y=1) = 2x^y
f (generic function with 2 methods)

julia> methods(f)
# 2 methods for generic function "f":
f(x) at none:1
f(x, y) at none:1

julia> f(1)
2

julia> f(2)
4

julia> f(2,2)
8

默认参数语法只是简单地生成了一个仅有一个参数的第二个方法，该方法调用带有默认值的两个参数形式。因此，f(x, y=1) = 2x^y 等价于定义了两个方法，其中一元方法只是调用二元方法，并为第二个参数提供默认值：

julia> f(x, y) = 2x^y
f (generic function with 1 method)

julia> f(x) = f(x, 1)
f (generic function with 2 methods)

- StefanKarpinski

---

这非常清晰易懂。谢谢。 - dopatraman