Why does it matter where I place return in above code?

New to Julia
,
1

I’ve tried making a simple Greatest Common Denominator code but output differs depending on where I use return.

First is the code that works as intendent. By using else statement, as far as I understand return runs only once and code terminates.

function GCD(a, b, r)
    n::Int64 = max(a, b)
    k::Int64 = min(a, b)
    z = n-k
    println("z is $z, n is $n, k is $k, Round $r")

    if ((z>=1) | (k<=1))
        println("GTD not yet Found!")
        GCD(z, k, r+1)
    else
        println("GTD is $k")
        return k, r
    end


    #println("GTD is $k")
    #return k, r
end

The output for this code using GCD(32, 12) is as expected (4, 4).

This is the full output, if needed:

z is 20, n is 32, k is 12, Round 0
GTD not yet Found!
z is 8, n is 20, k is 12, Round 1
GTD not yet Found!
z is 4, n is 12, k is 8, Round 2
GTD not yet Found!
z is 4, n is 8, k is 4, Round 3
GTD not yet Found!
z is 0, n is 4, k is 4, Round 4
GTD is 4
(4, 4)

Now, if we remove else statement and use the code in the comment at the bottom, like that:

function GCD(a, b, r)
    n::Int64 = max(a, b)
    k::Int64 = min(a, b)
    z = n-k
    println("z is $z, n is $n, k is $k, Round $r")

    if ((z>=1) | (k<=1))
        println("GTD not yet Found!")
        GCD(z, k, r+1)
    end


    println("GTD is $k")
    return k, r
end

Now, code returns

z is 20, n is 32, k is 12, Round 0
GTD not yet Found!
z is 8, n is 20, k is 12, Round 1
GTD not yet Found!
z is 4, n is 12, k is 8, Round 2
GTD not yet Found!
z is 4, n is 8, k is 4, Round 3
GTD not yet Found!
z is 0, n is 4, k is 4, Round 4
GTD is 4
GTD is 4
GTD is 8
GTD is 12
GTD is 12
(12, 0)

What I don’t understand is why the last println statement repeats itself, its as if the code is running in backward, or running the part of the code that hasn’t ran in previous rounds. Why is that?

Thank you for your answer!

2

In the second version, after the top-level GCD(z, k, r+1) is called, the final values of k and r are returned but not used. We then still continue with the rest of the code, which prints the old value of k and returns the initial pair k, r. This explains the last GTD is 12 print and return value of (12, 0). The other (earlier) prints are from the GCD(z, k, r+1) calls at other recursion depths (which return earlier).

If you just use return GCD(z, k, r + 1), the problem is solved.

function GCD(a, b, r)
    n::Int64 = max(a, b)
    k::Int64 = min(a, b)
    z = n-k
    println("z is $z, n is $n, k is $k, Round $r")
    
    if ((z>=1) | (k<=1))  # (It's better to use ||)
        println("GTD not yet Found!")
        return GCD(z, k, r+1)  # <------
    end
    
    println("GTD is $k")
    return k, r
end

julia> GCD(32, 12, 0)
z is 20, n is 32, k is 12, Round 0
GTD not yet Found!
z is 8, n is 20, k is 12, Round 1
GTD not yet Found!
z is 4, n is 12, k is 8, Round 2
GTD not yet Found!
z is 4, n is 8, k is 4, Round 3
GTD not yet Found!
z is 0, n is 4, k is 4, Round 4
GTD is 4
(4, 4)
2 Likes
3

What you might be missing is that every call to GCD eventually returns. At that point, execution continues – the next line of code after the call will be executed.

In the first version of your code, if GCD is called, the next line is an else block (which is skipped), and the function returns nothing.

In the second version, after GCD returns, a message is printed unconditionally. Maybe this code will make the difference clear:

function GCD(a, b, r)
                   n::Int64 = max(a, b)
                   k::Int64 = min(a, b)
                   z = n-k
                   println("z is $z, n is $n, k is $k, Round $r")

                   if ((z>=1) | (k<=1))
                       println("GTD not yet Found!")
                       GCD(z, k, r+1)
                   end


                   println("GTD is $k (round $r)") # modified to print the round
                   return k, r
               end

producing

julia> GCD(32,12,0)
z is 20, n is 32, k is 12, Round 0
GTD not yet Found!
z is 8, n is 20, k is 12, Round 1
GTD not yet Found!
z is 4, n is 12, k is 8, Round 2
GTD not yet Found!
z is 4, n is 8, k is 4, Round 3
GTD not yet Found!
z is 0, n is 4, k is 4, Round 4
GTD is 4 (round 4)
GTD is 4 (round 3)
GTD is 8 (round 2)
GTD is 12 (round 1)
GTD is 12 (round 0)
(12, 0)

The rounds go from 4 to 0 because the GCD functions are returning from the end of the stack to the start. The final (12,0) is the return value of the first call to GCD.

1 Like
4

So, just to make clear.
Essentially, what I’m calling GCD every time does is create a new instance of the function, while the previous one stays at GCD(z, k, r+1) till it finishes.
Than because the one that was ran last finishes first every other finishes after it and replaces the final value, to get the last answer?
Which means that implementation like that is very inefficient?

5

Yes, that description sounds correct. As for efficiency, in general recursion is not very efficient; its main advantage is that it can express some algorithms very elegantly (or just more simply).

3 Likes
6

Isn’t this a bit oversimplified? Sure, there is a bit of overhead since you need to store the call stack, but typically* you wouldn’t really care. There are of course situations where a naive recursive implementation is much worse than a naive iterative one (like the standard Fibonacci example), but in the situation of the standard Euclidean algorithm for GCD, I wouldn’t worry about it:

using BenchmarkTools

function GCD_rec(a, b)  # Enforce symmetry between a and b
    a >= b && return _GCD_rec(a, b)
    return _GCD_rec(b, a)
end

function _GCD_rec(a, b)  # a >= b
    b == 0 && return a
    return _GCD(b, a % b)
end

function GCD_it(a, b)
    a >= b && return _GCD_it(a, b)
    return _GCD_it(b, a)
end

function _GCD_it(a, b)
    while b > 0
        a, b = b, a % b
    end
    return a
end

@btime GCD_rec(9876543212345678987654321, 1234567898765432123456789)
#   246.193 ns (0 allocations: 0 bytes)
# 1

@btime GCD_it(9876543212345678987654321, 1234567898765432123456789)
#   373.659 ns (0 allocations: 0 bytes)
# 1

*For these inputs and the algorithm using only - instead of % you would get an StackOverflowError in the recursive implementation, though.

1 Like
7

I also think it sounds oversimplified. Recently I implemented a graph algorithm involving a recursive depth first search. Unfortunately stack overflow was a real problem for badly-behaved input, so I needed to to replace the recursion with a manual stack, which incurred a 30% slowdown. There are probably ways to recover some of that performance but if you need to maintain the stack information anyway and don’t need to worry about stack overflow, my first choice would be to try with recursion.

1 Like
8

Regarding recursion vs loops, another benefit of recursion, relevant when the recursion depth is known at compile time, is that it doesn’t reuse the same variable for different values. This is relevant for performance when the values are of different types, allowing type stable code, assuming unrolling.

9

It was intended to be just “simplified” – in retrospect, I might have added a stronger caveat than “in general”.

1 Like