# How to return a value in this recursive function?

HI,

I have a Zipper tree and try to label (with integers) the nodes in pre-order.

When the function detects state == index it continues processing

instead stopping the processing and return the state value.

See this code:

``````
def find_node( nil, _, _), do: nil

def find_node(_ , state), do: {:ok, state}

def find_node(node, index, counter) do

v = value(node)

Agent.update(counter, fn x -> x + 1 end )
state = Agent.get(counter, &(&1))

if index == state do

#-------------------------------------------------------------
#At his point the function should stop and return with
#the state equal to index
#-------------------------------------------------------------

end

find_node(left(  node), index, counter)

find_node(right( node), index, counter)

end
``````

You canât do an Â»early returnÂ« in Elixir. You will need to use `case`, `cond` or `with` instead. There is a very helpful guide on the Elixir website about case, cond and if and also a good section about with.

Note that the way youâve set up the function right now, will also not work with your two `find_node/3` calls. The result of the first `find_node` will simply be discarded.

So maybe you should do something like this instead:

``````if index == state do
index
else
with nil <- find_node(left(node), index, counter) do
find_node(right(node), index, counter)
end
end
``````

Like this, the function will return `index` if `index == state`. If it finds a node on the left side, it will return that, otherwise it will return the result of the `find_node` call for the right side.

Actually thatâs not entirely accurate (even though in principle with âreturnâ you are correct). The problem is that other programming languages have put a bias in peoples minds that `throw` is an error mechanism - well in Erlang/Elixir it isnât - `throw` simply allows the function to âthrowâ (rather than âreturnâ) a value up in the air and float it up the calling chain to however will bother to âcatchâ it. Thatâs why there are three different âcatchâ classes/categories:

• `:error` - runtime errors which in Elixir can also be handled via `rescue`
• `:exit` - to catch exits, i.e. `exit(reason)` from within the process (being a target of `Process.exit` cannot be âcaughtâ - you have to trap exits (with `Process.flag(:trap_exit,true)`) and process `:EXIT` messages). These should be treated as the true exceptions in Elixir/Erlang.
• values which are simply âthrownâ.

Learn You Some Erlang shows a non-failure use case of `throw` - an example of a tree search implementation which `throw`s the found value back to the root call of the search where the thrown value is caught.

3 Likes

As an aside, why are you using the agent like a mutable variable? just keep the counter as a function argument, using Agents as mutable state in this way is a misuse of Agents.

3 Likes

Instead of requiring the use of an âearly returnâ, you can just return from your recursion here without problems.

Something like:

``````# Public API: Returns {:ok, value_of_node_at_target_index} or {:error, index}.
def find_node(zipper_tree, target_index), do: find_node(zipper_tree, target_index, 0)

# Base case: Empty (sub)tree
defp find_node(nil, target_index, current_index), do: {:error, current_index}

# Recursive case: Try current node, or left subtree, or right subtree.
defp find_node(zipper_tree, target_index, current_index) do
if target_index == current_index
{:ok, value(zipper_tree)}
else
with {:error, left_child_index}  <- find_node(left(zipper_tree),  index, current_index + 1)),
do:  find_node(right(zipper_tree), index, left_child_index + 1))
end
end
``````

Other notes:

• What are the first two function clauses in your example code for? At least the second one only takes two parameters and not three.
• Either use `some_value | nil` or `{:ok, value} | {:error, error_msg}` as return values, but mixing them is probably not such a good idea as it is less explicit in what is going on.
• You really do not need an agent here, if you just thread the index you are currently looking at to the recursive function calls (which my code example shows).
• Just try the current index or otherwise the first non-error child tree.

Hi guys,

I agree the second clause is wrong.

My problem is to replace a random selected subtree from tree A with a random selected subtree from tree B. Each tree is a expression. One (sub)criteria was that only branch nodes, determined by a logical or arithmetic operator, should be selected. But there could be a number of the same operators (e.g. and, and, +, +, +, *, *, etc.) in the tree! To select (random) one of them I had to use a target_index. I agree, it is a trick.

Here you find the adapted code which give the required index and the subtree.

``````  def find_node( nil, _, _), do: nil

def find_node(node, index, counter) do

v = value(node)

Agent.update(counter, fn x -> x + 1 end )
state = Agent.get(counter, &(&1))

if index == state do
{index, node.focus}
else
with  nil <- find_node(left(node), index, counter) do
find_node(right(node), index, counter)
end
end
end

#--------------------------------------------------------------------

test "Find target_index N in zipper" do

root = t11() |> from_tree

{:ok, counter} = Agent.start(fn -> 0 end )

target_index = 8

{current_index, focus } = find_node(root,target_index,counter)

assert current_index == target_index

end

#--------------------------------------------------------------------

test "Find node.focus in zipper" do

root = t11() |> from_tree

{:ok, counter} = Agent.start(fn -> 0 end )

target_index    = 8

{current_index, focus } = find_node(root,target_index,counter)

assert  focus  ==  %BinTree{left: %BinTree{left: nil, right: nil, value: 3},
right: %BinTree{left: nil, right: nil, value: "c"}, value: "*"}
end

``````