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

**URL:** <https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484>\
**Category:** New to Julia\
**Tags:** question, recursion\
**Created:** [October 19, 2024, 3:48pm UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484 "2024-10-19T15:48:38Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![matic\_lauko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/matic_lauko/32/27770_2.png) [@matic\_lauko](https://discourse.julialang.org/u/matic_lauko)\
**Post date:** [October 19, 2024, 3:48pm UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/1 "2024-10-19T15:48:38Z")

</div>

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.

```julia
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:

```julia
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:

```julia
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

```julia
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!

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [October 19, 2024, 4:19pm UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/2 "2024-10-19T16:19:28Z")

</div>

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.

```julia
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-repl
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)

```

---

<div class="post-metadata">

**Author:** ![mbaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbaz/32/17295_2.png) [@mbaz](https://discourse.julialang.org/u/mbaz)\
**Post date:** [October 19, 2024, 4:25pm UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/3 "2024-10-19T16:25:49Z")

</div>

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:

```julia
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
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`.

---

<div class="post-metadata">

**Author:** ![matic\_lauko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/matic_lauko/32/27770_2.png) [@matic\_lauko](https://discourse.julialang.org/u/matic_lauko)\
**Post date:** [October 19, 2024, 5:20pm UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/4 "2024-10-19T17:20:35Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![mbaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbaz/32/17295_2.png) [@mbaz](https://discourse.julialang.org/u/mbaz)\
**Post date:** [October 19, 2024, 6:38pm UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/5 "2024-10-19T18:38:13Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [October 20, 2024, 8:24am UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/6 "2024-10-20T08:24:31Z")

</div>

> [@mbaz](#):
>
> As for efficiency, in general recursion is not very efficient

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:

```julia
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.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [October 20, 2024, 9:40am UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/7 "2024-10-20T09:40:51Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 20, 2024, 2:58pm UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/8 "2024-10-20T14:58:02Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mbaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbaz/32/17295_2.png) [@mbaz](https://discourse.julialang.org/u/mbaz)\
**Post date:** [October 20, 2024, 4:55pm UTC](https://discourse.julialang.org/t/why-does-it-matter-where-i-place-return-in-above-code/121484/9 "2024-10-20T16:55:36Z")

</div>

> [@eldee](#):
>
> Isn’t this a bit oversimplified?

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