 # How to return the current node in a recursive iteration, if there is a condition?

So, first, a clarification: this question is in essence very similar to Append an element to a recursive list iteratively and Convert tail-recursive form to iterative form?, however, there is a crucial difference, and it's the one that causes the problem - the conditional return of the current node.

This is a relatively barebones version of a list iterator:

``````struct Node {
node_data: Option<Box<Node>>,
}

impl Node {
fn find_iterative(&mut self) -> &mut Node {
let mut current = self;

loop {
match current.node_data {
Some(ref mut child) => {
if Self::some_condition() {
return current;
} else {
current = child;
}
}
_ => {
panic!("");
}
}
}
}

fn some_condition() -> bool {
true
}
}
``````

Now, I get an error on the `return current;`. I've tried the conventional workarounds:

• using a temporary value for `current`;
• wrapping `current` in curly braces (in the `match` expression).

none of those worked. The culprit is the conditional block (intended as a whole, not just the `if` expression), which I can't remove, because it's crucial.

The only two ways of making it work are:

• converting the logic to recursive;
• using the `polonius` Rust flag.

Is there some workaround/solution I can use, instead of the two above?

The problem is that `current.node_data` is holding exclusive access to `current` for the entire `match` body. If you refactor that to hold a boolean test result instead of a mutable reference, it’ll fix the problem:

``````            if current.node_data.is_some() {
if Self::some_condition() {
return current;
} else {
current = current.node_data.as_mut().unwrap();
}
} else {
panic!("");
}
``````

Transforming the `if` into a match guard also seems to make the borrow checker happy:

``````            match current.node_data {
Some(_) if Self::some_condition() => {
return current;
}
Some(ref mut child) => {
current = child;
}
None => {
panic!("");
}
}
``````

This only works if `Self::some_condition()` is not an expression that uses `child` mutably -- you can, perhaps surprisingly, bind `child` in the pattern by shared reference.

3 Likes

@trentj's observation is actually correct - my example was oversimplified.

The suggested strategy is still a clean, working, solution; this is the working, complete, version of the logic:

``````struct Node<T: PartialOrd + Copy> {
node_data: Option<(T, Box<Node<T>>)>,
}

impl<T: PartialOrd + Copy> Node<T> {
fn iterative_ordered_push(&mut self, value: T) {
let mut current = self;

loop {
match current.node_data {
Some((ref current_value, _)) if *current_value > value => {
break;
}
Some((_, ref mut child)) => {
current = child;
}
_ => {
break;
}
}
}

current.push_front(value);
}

fn push_front(&mut self, _value: T) {
// Push to front of the self node
}
}
``````

Thanks!

1 Like