Problems with implementing return on recursive function with Julia

Question

I have implemented the next code for going down and right in a grid, and I am trying to implement some sort of counting like return +1 but I can't, if I'm forced to use global it makes the runtime considerably longer (like times 8 though it varies with the number of iterations). Please advise on how to code correctly in this language.

I also thought about using pointers like in C but had hard time implementing it

function numOfPaths(NominalSize,x,y)
    (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
    (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
    (x >= NominalSize && y>=NominalSize) && global count+=1;
end
count = 0;
t1 = @elapsed numOfPaths(16,0,0)

2nd version with Ref instead of using global, pretty much same horrible performance.

function numOfPaths(NominalSize,x,y)
   (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
   (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
   ((y >= NominalSize) && (x >= NominalSize)) && (ref[] += 1 ;)
end
count = 0;
ref = Ref(count)
t1 = @elapsed anse = numOfPaths(15,0,0)

Answer 1

With the current state of the Julia compiler I think you have two options (assuming you do not change the logic of your code).

The first one is leave things as they are in your code, but change count to be a global const. However, as you want to mutate it you have to introduce some wrapper, a natural one is Ref. So you can go with something like:

const count = Ref(0)
function numOfPaths(NominalSize,x,y)
    (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
    (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
    (x >= NominalSize && y>=NominalSize) && global (count[] +=1)
end
count[] = 0
@time numOfPaths(16,0,0)
count[]

Now you could pass around count like this:

function numOfPaths(NominalSize,x,y, count=Ref(0))
    (x < NominalSize) && numOfPaths(NominalSize,x+1,y, count)
    (y < NominalSize) && numOfPaths(NominalSize,x,y+1, count)
    (x >= NominalSize && y>=NominalSize) && (count[] +=1)
    return count[]
end

as a parameter, but it will be a bit slower.

Finally (and this is an option that is a bit faster than the first one and is recommended) you can perform the accumulation of count without passing it as an argument (this time it will be just an integer):

function numOfPaths(NominalSize,x,y)
    count = 0
    x < NominalSize && (count += numOfPaths(NominalSize,x+1,y))
    y < NominalSize && (count += numOfPaths(NominalSize,x,y+1))
    x >= NominalSize && y>=NominalSize && (count+=1)
    return count
end

---

EDIT:

Additionally let me comment on what does not work. Naturally you would want to rewrite your function like this:

function numOfPaths(NominalSize,x,y)
    function f(x, y)
        x < NominalSize && f(x+1,y)
        y < NominalSize && f(x,y+1)
        x >= NominalSize && y>=NominalSize && (count+=1)
    end

    count = 0
    f(x, y)
    return count
end

Unfortunately, currently such code is slow, as Julia is boxing count:

julia> @code_warntype numOfPaths(16, 0, 0)
Variables
  #self#::Core.Compiler.Const(numOfPaths, false)
  NominalSize::Int64
  x::Int64
  y::Int64
  f@_5::Core.Box
  count@_6::Core.Box
  f@_7::Union{}
  f@_8::Union{}
  count@_9::Union{}

Body::Any
1 ─       (f@_5 = Core.Box())
│         (count@_6 = Core.Box())
│   %3  = Main.:(var"#f#3")::Core.Compiler.Const(var"#f#3", false)
│   %4  = Core.typeof(NominalSize)::Core.Compiler.Const(Int64, false)
│   %5  = Core.apply_type(%3, %4)::Core.Compiler.Const(var"#f#3"{Int64}, false)
│   %6  = f@_5::Core.Box
│   %7  = %new(%5, NominalSize, %6, count@_6)::var"#f#3"{Int64}
│         Core.setfield!(f@_5, :contents, %7)
│         Core.setfield!(count@_6, :contents, 0)
│   %10 = Core.isdefined(f@_5, :contents)::Bool
└──       goto #3 if not %10
2 ─       goto #4
3 ─       Core.NewvarNode(:(f@_8))
└──       f@_8
4 ┄ %15 = Core.getfield(f@_5, :contents)::Any
│         (%15)(x, y)
│   %17 = Core.isdefined(count@_6, :contents)::Bool
└──       goto #6 if not %17
5 ─       goto #7
6 ─       Core.NewvarNode(:(count@_9))
└──       count@_9
7 ┄ %22 = Core.getfield(count@_6, :contents)::Any
└──       return %22

Hopefully in the future this will get resolved (it is a known issue).

---

EDIT 2

First let me comment what to do if you wanted to make this code run faster. In this case instead of recursion one can use dynamic programming, e.g.:

function numOfPaths(NominalSize, x, y)
    y, x = minmax(x, y)
    a = ones(BigInt, NominalSize + 1 - y)
    for i in 2:NominalSize - x + 1
        i > length(a) || (a[i] = 2 * a[i])
        for j in i+1:length(a)
            a[j] += a[j-1]
        end
    end
    return a[end]
end

(note that I am using BigInt here, as with this code you can test values that are much larger than the range of Int64 type; if you would want to be even faster just switch BigInt to Int in the code, but then for NominalSize greater than 33 you will get an overflow)

---

Now, going to the question of @Alex Zh why the second code runs slowly. You can run @code_warntype on it to learn the following:

julia> function numOfPaths(NominalSize,x,y)
          (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
          (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
          ((y >= NominalSize) && (x >= NominalSize)) && (ref[] += 1 ;)
       end
numOfPaths (generic function with 1 method)

julia> count = 0;

julia> ref = Ref(count)
Base.RefValue{Int64}(0)

julia> @code_warntype numOfPaths(15,0,0)
Variables
  #self#::Core.Compiler.Const(numOfPaths, false)
  NominalSize::Int64
  x::Int64
  y::Int64

Body::Any
1 ─ %1  = (x < NominalSize)::Bool
└──       goto #3 if not %1
2 ─ %3  = (x + 1)::Int64
│         Main.numOfPaths(NominalSize, %3, y)
└──       goto #3
3 ┄ %6  = (y < NominalSize)::Bool
└──       goto #5 if not %6
4 ─ %8  = (y + 1)::Int64
│         Main.numOfPaths(NominalSize, x, %8)
└──       goto #5
5 ┄ %11 = (y >= NominalSize)::Bool
└──       goto #9 if not %11
6 ─ %13 = (x >= NominalSize)::Bool
└──       goto #8 if not %13
7 ─ %15 = Base.getindex(Main.ref)::Any
│   %16 = (%15 + 1)::Any
│         Base.setindex!(Main.ref, %16)
└──       return %16
8 ─       return false
9 ─       return false

Now in the line:

%15 = Base.getindex(Main.ref)::Any

you see that when Julia fetches ref from Main it does not know what is its type, as it is a global variable that is not a constant. Therefore the compiler is not able to generate an efficient machine code, as the type of ref has to be resolved at run time (not at compile time).

Now consider the following change (you need to restart Julia to test it):

ulia> function numOfPaths(NominalSize,x,y)
          (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
          (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
          ((y >= NominalSize) && (x >= NominalSize)) && (ref[] += 1 ;)
       end
numOfPaths (generic function with 1 method)

julia> count = 0;

julia> const ref = Ref(count)
Base.RefValue{Int64}(0)

julia> @code_warntype numOfPaths(15,0,0)
Variables
  #self#::Core.Compiler.Const(numOfPaths, false)
  NominalSize::Int64
  x::Int64
  y::Int64

Body::Union{Bool, Int64}
1 ─ %1  = (x < NominalSize)::Bool
└──       goto #3 if not %1
2 ─ %3  = (x + 1)::Int64
│         Main.numOfPaths(NominalSize, %3, y)
└──       goto #3
3 ┄ %6  = (y < NominalSize)::Bool
└──       goto #5 if not %6
4 ─ %8  = (y + 1)::Int64
│         Main.numOfPaths(NominalSize, x, %8)
└──       goto #5
5 ┄ %11 = (y >= NominalSize)::Bool
└──       goto #9 if not %11
6 ─ %13 = (x >= NominalSize)::Bool
└──       goto #8 if not %13
7 ─ %15 = Base.getindex(Main.ref)::Int64
│   %16 = (%15 + 1)::Int64
│         Base.setindex!(Main.ref, %16)
└──       return %16
8 ─       return false
9 ─       return false

Now I have made ref a global const. This tells the compiler that ref is guaranteed not to change its type. Therefore you have:

7 ─ %15 = Base.getindex(Main.ref)::Int64

as this time the compiler has all type information it needs, so a much more efficient machine code can be generated.