Understanding recursion without base case in Julia

Question

This snippet is from the implementation of Rational Numbers in 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!

# ...

See how the // function is implemented and then used with infix notation? How does this actually return a value?

When I saw this code I interpreted it like this:

1. The // function is called with a Rational and an Integer.
2. But then it makes a recursive call with no other arguments.

#2 is the one that really confuses me. Where does the recursion within data structure end? How does // return a value if it is constantly evaluating nothing?

Please help me understand this.

Answer 1

This works because of one of the most fundamental features of Julia: multiple dispatch. In Julia, functions can have many methods which apply to various combinations of argument types, and when you call a function, Julia invokes the most specific method which matches the type of all the arguments that you called it with. The // call in the method definition you posted defines rational-integer // in terms of integer-integer // – so it isn't actually recursive because the method doesn't call itself, it calls a different method that is part of the same "generic function".

To understand how multiple dispatch works in this case, let's consider the evaluation of the expression (3//4)//6. We'll use the @which macro to see which method each function call invokes.

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

Since 3//4 is a Rational{Int} <: Rational and 6 is an Int <: Integer, and no other more specific methods apply, this method is called:

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

The current version of the method is actually slightly more complicated than what you posted because it's been modified to check for integer overflow – but it's essentially the same, and it's easier to understand the older, simpler version, so I'll use that. Let's assign x and y to the arguments and see what method the definition calls:

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

As you can see, this expression doesn't call the same method, it calls a different method:

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

This method simply calls the Rational constructor which puts the ratio of n and d into lowest terms and creates a Rational number object.

It is quite common to define one method of a function in terms of another method of the same function, in Julia. This is how argument defaults work, for example. Consider this definition:

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

The default argument syntax simply generates a second method with only onee argument, which calls the two-argument form with the default value. So f(x, y=1) = 2x^y is exactly equivalent to defining two methods, where the unary method just calls the binary method, supplying a default value for the second argument:

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

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