Calling another recursive function inside a recursive function

So, I have this problem where I have to call a recursive function inside another recursive function. The reason why I am opting for this is that I have to implement a while loop in Elixir which calls a function inside of it recursively. An example of what I want to do in Python is the following:

def function(map, newList, origin):
        mylist = map[origin]
        while mylist:
            nextVal = mylist.pop()
            function(map, newList, origin)
        
	newList.append(map, newList, origin)

Over here, we first get a value from map, then loop over mylist until it size becomes zero. Inside this loop, I extract the last element of the list and then pass that into the function as the updated origin.

My implementation of this is the following:

defmodule MyFunction do
  def function(map, newList, list, origin) do
    if length(list) > 0 do
      function(map, newList, origin)
    else
      newList
    end
  end

  def function(map, newList, origin) do
    list = map[origin]
    origin = hd(list)
    list = tl(list)

    newList = function(map, newList, list, origin)
    [origin | newList]
  end
end

map basically contains strings as keys and lists as its values, which contains multiple strings. An example of this is:

%{"HELLO" -> ["SKY"],
"SKY" -> ["WORLD"],
"KING" -> ["NEW"],
"WORLD" -> ["KING"]
}

origin over here is a string such as HELLO. This, however, only adds the first origin value to newList. Does anyone know what I am doing wrong?

Any help will be appreciated. Been stuck on this for too long :cry:

Hate to be that guy but… why? There are other ways of achieving the same in Elixir.

We can help you with them as opposed to trying to directly translate Python code.

2 Likes

My understanding of Elixir is still very weak so I have to rely on languages that help me better understand the problem.

As for the problem, assuming origin is HELLO, what I want to do is basically something like the following:

origin = "HELLO"
map = 
%{"HELLO" -> ["SKY"],
"SKY" -> ["WORLD"],
"KING" -> ["NEW"],
"WORLD" -> ["KING"]
}

I want to get the origin value from the map which would be [“SKY”,“WORLD”]. Then, I want to replace the origin with SKY, remove the first value of list (This is to stop the recursion coming up next. Basically, it stops when empty list is encountered) and then recursively call the function with the replaced origin which starts the process again till the base condition gets meet.

I also want to store the values of these origin in a list and return that list at the end.

Basically, I want to traverse over a map, keep on adding the origins into another list and this continues until we encounter an empty list after which the process ends.

It’s unclear to me what you’re trying to achieve in the algorithm, but looks like some sort of graph traversal. Your Python version is incomplete (what’s the definition of function with 1 arg?). Writing the Elixir code will be much easier if you first try to express the algorithm in the pseudo-code.

3 Likes

In your example, how should the final result look like?

1 Like

You are fighting an uphill battle, man – writing imperative / OOP code which you then try and translate to FP is definitely burning much more watts of energy in your brain than it should.

To avoid the The XY Problem, can you tell us what exactly is desired? What’s the expected shape of the input and what’s the expected output, and what’s the goal?

7 Likes

@dimitarvp @andreaseriksson @stefanchrobot Apologies for not presenting the problem correctly. Also, there was a typo in the original Python code. I have corrected both that and the example.

So, I have the following map:

map = 
%{"HELLO" -> ["SKY"],
"SKY" -> ["WORLD"],
"KING" -> ["NEW"],
"WORLD" -> ["KING"]
}

So what I want to do is, first of all, we will start with an origin which in this case is HELLO. Now, using this we will keep on visiting all the keys of the map till all of them have been visited.

So, if we have origin = “HELLO”, we will get its value which is ["SKY"]. After this, we extract the word “SKY” and make it our new origin. Now, we run the DFS (recursive call on this new origin) which would give us the value ["WORLD"]. We will then keep on repeating this process until all the keys have been visited. I’m basically trying to run a DFS.

My final output would be: ["HELLO", "SKY", "WORLD", "KING", "NEW"].

1 Like

Not sure if is the best solution but maybe something like this. I think this can also be achieved with an Enum.reduce but this is more clear

defmodule Test do
  def search_orig(input_map, nil, res), do: res

  def search_orig(input_map, key, res) do
    res = res ++ [key]
    next_key =
      case input_map[key] do
        [k | _] -> k
        nil -> nil
      end
    search_orig(input_map, next_key, res)
  end

end

And you call the function like this


iex(14)> input
%{
  "hello" => ["sky"],
  "king" => ["new"],
  "sky" => ["world"],
  "world" => ["king"]
}
iex(15)> Test.search_orig(input, "hello", [])
["hello", "sky", "world", "king", "new"]
3 Likes

This is perfect! Thank you so much :fist_left:

1 Like

You should make use of pattern matching…

def function(_map, newList, [], _origin), do: newList
def function(map, newList, list, origin), do: function(map, newList, origin)

This is expensive…

if length(list) > 0 do

You should match on [], or use Enum.empty? instead

What about this?

[origin | list] = map[origin]

Using local variables can be replaced by pipelines |>

5 Likes

@belteconti You’ve got several comments on how to make your code more elixirish. My advice is that now you share your solution and fellow programmers can build on that code making comments.

3 Likes

I sometime feel sorry when You try to translate code from Python to Elixir, it must be damn hard :slight_smile:

But I know what it feels, because I am trying to learn LFE, to understand what Lisp is…

I spent one day on one function.

(defmodule day5 (export (load_data 0)))
(defun load_data ()
    (let 
        (((tuple 'ok bin) (file:read_file "input.txt"))) 
        (string:split bin "\n" 'all)))

If You want to see some Elixir code, You can have a look at the Advent of Code topics. It’s a good opportunity to see how people resolve problems. In very different way…

Without loop and mutability.

2 Likes

Thank you for all your feedback and amazing responses. The solution that I came up with was basically highly influenced by @alejolcc and using the instructions of @kokolegorille. Following is what I came up with:

defmodule MyFunction do
  # When origin is finally nil, return the new_list
  def function(_map, new_list, nil), do: new_list

  def function(map, new_list, origin) do
    # Add the node to new_list
    new_list = [origin | new_list]

    # Update the origin and map (latter is done to end recursion)
    {new_origin, map} = 
      case map[origin] do
        # Extract the top and rest of the list from map
        [top | rest] -> {top, Map.put(map, origin, rest)}
        [] -> {nil, map} 
        nil -> {nil, map}
      end

    # Call the function again to start recursion
    function(map, new_list, new_origin)
  end

I had to update the map as well since there might be a case where the map key might have more than one value and in this case, there is a risk of infinite recursion happening if the map isn’t updated. In addition, there is a slight issue with this solution and that is also when a map key has more than one value. For example, if we have the following map and our origin is HELLO:

%{"SKY" => ["WORLD”, “HELLO"],
"HELLO" => ["SKY”,  “WORLD"],
"WORLD" => ["SKY”]
}

The output that the above code will provide is: ["HELLO", "SKY", "WORLD", "SKY", "HELLO", "WORLD"] when it rather should be ["HELLO", "SKY", "HELLO", "WORLD", "SKY", "WORLD"]. Basically, when a map key has more than one value, then start adding the key value from the end of the list rather than the top since a DFS is being done.

However, I’m not entirely sure how this can be achieved.

3 Likes

That looks Good. Much better!

Now you can apply this if you want:

  1. use a descriptive name for your “function”.
  2. use a function head that describe your argument by reading your first functions clause one cannot know what the last argument is about.
  3. use a spec to document how your funtion works.
  4. add guards to your API.
  5. avoid use of conditional (while not mandatory, it is good to know and common practice) so you call your functions recursively (create a helper function if needed)

Bonus:
6. cater for recursive calls. Keep track in your helper function of all the keys that have already been used, so raise if a recursive call happens, or return the accumulated list up to then. Alternatively you can update your map and remove that key when taken.

4 Likes