Recursive functions

New to Julia
1

Hello,
Consider the following recursive function:

function decToBin(n)
    if n > 0
        decToBin(n ÷ 2)
        print("$(n % 2)")
    end
end

For example, n=13. The n is greater than 0 and the line decToBin(n ÷ 2) is executed. Does the function get called again and the statement print("$(n % 2)") is not executed?

Thank you.

2

Correct, that’s how recursion works

3

I might have misunderstood the question, but I don’t think that’s correct.

The print is of course executed for each call to decToBin where n is > 0, it just happens after the call to decToBin finishes. So for n = 13 the function will first call itself (*) and then print will be called with 13 % 2.

(*) Of course when it calls itself with 13 ÷ 2 = 6, it will first call itself (**) and then print will be called with 6 % 2.

(**) Of course when it calls itself with 6 ÷ 2 = 3, it will first call itself (***) and then print will be called with 3 % 2.

(***) …

The lowest “level” of this recursion is when the first print will happen, then the one in the level above, then the one above etc. until (*) finishes and the original function can continue with the original print statement print("$(13 % 2)") which will appear last on the screen (although the function is called first).

Or in another visual way:

function decToBin(n)
    if n > 0
        decToBin(n ÷ 2)     ----->  if (n ÷ 2) > 0
        print("$(n % 2)")               decToBin((n ÷ 2) ÷ 2)   -----> if ((n ÷ 2) ÷ 2) > 0
    end                                 print("$((n ÷ 2) % 2)")           ...
    (return nothing)                end

(I added the implicit return nothing here to illustrate that the return value of print would be returned, which is nothing here).

This would be very different to (note the extra return statement which prevents any print from being executed):

function decToBin(n)
    if n > 0
        return decToBin(n ÷ 2)
        print("$(n % 2)")
    end
end
5 Likes
4

Hi,
Thank you so much for your great answer.

1 Like