Why doesn't this return the intended value

New to Julia
1

Hi,

Background: this is the last part of my implementation of the huffman compression. The good news is,
it seems to work the print(decoded_string) give back the string it decoded before. But it does not return it. it returns nothing the value of decoded_string is "" initially.

other parameter are:
encoded_string: is a string with 1’s and 0’s.
key_encoding_array: an array of tuples with the structure Vector{Tuple{String, String,Int64}}

function rebuilding_message(encoded_string,key_encoding_array::Vector{Tuple{String, String,Int64}},decoded_string)

    if isempty(encoded_string)
       print(decoded_string)    
       return decoded_string
    else
       for i in key_encoding_array
            if length(encoded_string) >= i[3] && i[2] == encoded_string[1:i[3]]
               rebuilding_message(SubString(encoded_string,(i[3]+1)),key_encoding_array,string(decoded_string,i[1]))
            end
        end
    end
end

thanks in advance!

2

It’s because the else branch doesn’t return anything.

1 Like
3

Sorry, i don’t understand what you mean. The else branch does not return but it does contain a recursively call to the same function. The basecase of the recursion should have a return and it does. Can you otherwise show me what you mean?

4

you still need to return:


julia> function f(a)
           if a == 0
               return 0
           else
               for i = 1:1
                   f(a-1)
               end
           end
       end
f (generic function with 1 method)

julia> f(2)

julia> function f(a)
           if a == 0
               return 0
           else
               for i = 1:1
                   return f(a-1)
               end
           end
       end
f (generic function with 1 method)

julia> f(2)
0
1 Like
5

Isn’t this an example of a tail recursive function? Perhaps OP comes from a language where this is automatically optimized. There is an interesting discussion: tail call elimination · Issue #4964 · JuliaLang/julia · GitHub

6

Unless rebuilding_message modifies its arguments, which doesn’t seem to be true here, you want to return something from the else branch. Same as

function fib(n) 
    if n <= 1 
        return n 
    else 
        return fib(n-1) + fib(n-2)
    end 
end
7

uhh, no? This is not really a good example, did you try it without the return in the else clause? It works the exact same way. If the else pertains to an if that is the last expression in a method and the last line of the else has any value then that value is returned, as in any other method in Julia.

1 Like
8

I have put a return in the else statement. No change in result. I have adjusted some stuff but no solution yet.

9

What happens if key is not in the array? Then the loop finishes with nothing, no?

10

correct, hasn’t happened as far as I can tell. there is a print(decoded_string) just before the return. This starts out as “” and but does print out the correct text. I do think the construction of if statement - for loop - if statement seems to not work properly.

11

Something like this

function rebuilding_message(encoded_string,key_encoding_array::Vector{Tuple{String, String,Int64}},decoded_string)
    @show encoded_string, decoded_string
    if !isempty(encoded_string)
       for i in key_encoding_array
            if length(encoded_string) >= i[3] && i[2] == encoded_string[1:i[3]]
               decoded_string = rebuilding_message(SubString(encoded_string,(i[3]+1)),key_encoding_array,string(decoded_string,i[1]))
            end
        end
    end
    return decoded_string
end

@show rebuilding_message("abc", [("a", "a", 1), ("b", "b", 1), ("c", "c", 1)], "")

seems to be what you intended?

2 Likes
12

@goerch : no not really. The decoded_string start of as empty "". And with each recursion a character is added to the decoded_string and the encoded_string becomes smaller. Up to the point that the encoded_string is empty and the decoded_string is full.

i didn’t know that @show command though…that help with the debugging!

13

and is returned. That is what I believe to see in my REPL

(encoded_string, decoded_string) = ("abc", "")
(encoded_string, decoded_string) = ("bc", "a")
(encoded_string, decoded_string) = ("c", "ab")
(encoded_string, decoded_string) = ("", "abc")
rebuilding_message("abc", [("a", "a", 1), ("b", "b", 1), ("c", "c", 1)], "") = "abc"

?

Edit: tried a maybe better example

@show rebuilding_message("abc", [("d", "a", 1), ("e", "b", 1), ("f", "c", 1)], "")

and get

(encoded_string, decoded_string) = ("abc", "")
(encoded_string, decoded_string) = ("bc", "d")
(encoded_string, decoded_string) = ("c", "de")
(encoded_string, decoded_string) = ("", "def")
rebuilding_message("abc", [("d", "a", 1), ("e", "b", 1), ("f", "c", 1)], "") = "def"
14

That only returns to the previous stackframe, which ends up in the for loop of the previous call.

Loop blocks by default return nothing because it’s not well defined which of the loop iteration values should be returned. Thus you need to save whichever result you want to return and then return that after the loop is done.

2 Likes
15

@Sukera I get what you mean but something doesn’t make sense to me.I did a slight rewrite based on what @goerch. replaced the print with @show.

My problem is that if I do this I get the right result. How is that possible? @show gives me the correct string in the correct sequence back but adding a return somehow gives nothing. The explanation I have heard thus far make perfect sense if it wasn’t for the correct string first being given.

function rebuilding_message(encoded_string,key_encoding_array::Vector{Tuple{String, String,Int64}},decoded_string)
    if isempty(encoded_string)
        @show decoded_string
        return decoded_string
     else
        for i in key_encoding_array
             if length(encoded_string) >= i[3] && i[2] == encoded_string[1:i[3]]
                rebuilding_message(SubString(encoded_string,(i[3]+1)),key_encoding_array,string(decoded_string,i[1]))
             end
         end
     end
 end
16

@goerch I now get a string back but its complete jumbled. not reversed or something fixable. it’s basically now encrypted.:slight_smile:

Though it seems to work for your example.

17

Hi @AlexanderChen, what I tried to show you is how easy it should be to complete the M(inimal)W(orking)E(example) for others to check. Simply fill in the parameters of the call of rebuilding_message and we should find a way to make this work.

18

Having computed the correct string and returning it from the call stack are two different things - you’re printing it to the console, but not returning it from the function in the else branch. You’re not assigning the result if rebuilding_message in the recursion to anything, so its return value is ignored.

Try this instead:

function rebuilding_message(encoded_string,key_encoding_array::Vector{Tuple{String, String,Int64}},decoded_string)
    if isempty(encoded_string)
        return decoded_string
     else
        for i in key_encoding_array
             if length(encoded_string) >= i[3] && i[2] == encoded_string[1:i[3]]
                # actually return the value we get from the recursion further up the call stack
                return rebuilding_message(SubString(encoded_string,(i[3]+1)),key_encoding_array,string(decoded_string,i[1]))
             end
         end
     end
 end
1 Like
19

@Sukera I already tried this yesterday and did it now again. result is both identical namely nothing

20

Then I suspect there’s a bug in your logic. The only way nothing can be returned from there is if the if condition in the loop is never true, i.e. the recursion isn’t run in some call. Semantically it’s the same as this:

function rebuilding_message(...)
     if isempty(encoded_string)
        return decoded_string
     else
        for i in key_encoding_array
             if length(encoded_string) >= i[3] && i[2] == encoded_string[1:i[3]]
                # recursive call, only hit when the if is true
                return rebuilding_message(...)
             end
        end

        return nothing
     end
 end

Like I said above, for loops don’t implicitly return any value (i.e. the branch then returns nothing). Does that make more sense to you?

2 Likes