Simple recursive Fibonaci example. How to make it faster?

General Usage Performance
36 
function A(m,n)
    if iszero(m)
        n + one(n)
    elseif iszero(n)
        A(m - one(m), one(n))
    else
        A(m - one(m), A(m, n - one(n)))
    end
end

ccode = """
long A(long m, long n){
    long x;
    if (m == 0) {
        x = n + 1;
    } else if (n == 0) {
        x = A(m - 1, 1);
    } else {
        x = A(m - 1, A(m, n - 1));
    }
    return x;
}

""";
open("ackerman.c", "w") do io
    write(io, ccode)
end
run(`gcc -O3 -march=native -shared -fPIC ackerman.c -o libackerman.so`)
const AckerC = joinpath(pwd(), "libackerman.so")
Ac(m::Clong, n::Clong) = @ccall AckerC.A(m::Clong, n::Clong)::Clong

This yields:

julia> @time A(3,3)
  0.000005 seconds
61

julia> @time Ac(3,3)
  0.000003 seconds
61

julia> @time A(4, 1)
  4.537859 seconds
65533

julia> @time Ac(4, 1)
  1.829240 seconds
65533
5 Likes