Break a recursive loop

[Alvaro Perez]

Hi there,

something that I think should not be very difficult, but i'm struggling
with:

def find(name, where)
for father in where
if (father.name==name) then
found = thing
break
else
find(name, father.children)
end
end
found
end

I have an array with parent objects, some of them have children. I want
to find an object with the same name and return in, otherwise nil.

The problem is that, once I start searching inside the children of some
father, and I found what I'm looking for, I break the loop inside (array
father.children). But then the search continues in the level above. I
would like to break the complete search. How can it be done?

Thank you!!

 

[Stefano Crocco]

Alle luned=C3=AC 19 novembre 2007, Alvaro Perez ha scritto:

Hi there,

something that I think should not be very difficult, but i'm struggling
with:

def find(name, where)
for father in where
if (father.name=3D=3Dname) then
found =3D thing
break
else
find(name, father.children)
end
end
found
end

I have an array with parent objects, some of them have children. I want
to find an object with the same name and return in, otherwise nil.

The problem is that, once I start searching inside the children of some
father, and I found what I'm looking for, I break the loop inside (array
father.children). But then the search continues in the level above. I
would like to break the complete search. How can it be done?

Thank you!!

Not tested (and not sure I understand your code correctly. What's thing?):

def find(name, where)
where.each do |father|
found =3D if father =3D=3D name then thing
else find(name, father.children)
end
break found if found
end
end

If this doesn't work, you can try looking at the documentation for=20
Kernel#throw and Kernel#catch.

I hope this helps

Stefano

 

[Michel Boaventura]

You can set a variable and set it true if you find. Then inside the
loop, use it like this:
if (find = true) break

Or you can use exceptions to break the loop.

 

[_Stud]

Instead of breaking out of the loop, why don't you return the object
you found or return 'true'?

_Steve

 

[Alvaro Perez]

Instead of breaking out of the loop, why don't you return the object
you found or return 'true'?

_Steve

I tried but does not work if I want to return nil when I found
nothing...

 

[Michel Boaventura]

You can use the ObjectSpace Module, who give you acess of all objects
in the memory.

Take a look:
http://www.ruby-doc.org/core/classes/ObjectSpace.html#M006784

 

[Just Another Victim of the Ambient Morality]

Hi there,

something that I think should not be very difficult, but i'm struggling
with:

def find(name, where)
for father in where
if (father.name==name) then
found = thing
break
else
find(name, father.children)
end
end
found
end

I have an array with parent objects, some of them have children. I want
to find an object with the same name and return in, otherwise nil.

The problem is that, once I start searching inside the children of some
father, and I found what I'm looking for, I break the loop inside (array
father.children). But then the search continues in the level above. I
would like to break the complete search. How can it be done?

I don't understand, exactly, what you're doing but there are some things
that are obviously wrong with your code and some techniques you should
probably know to implement what you're doing.
First of all, have you tested your own code? Your find() method doesn't
even store the value of its recursive call. It might still work if that
recursive call is the last thing your method does but you explicitly
evaluate the variable "found," ensuring that the recursed value is never
returned since it can never be the last thing done.
Secondly, using literal for loops is very pythonic and, thus, un-ruby
like. Wouldn't you rather where.each through elements?
Finally, there are many different ways to solve your problem. If where
is enumerable, you can use the find method:

def weird_find(name, container)
container.find do |father|
if father.name == name
father # Is this what you're looking for?
else
weird_find(name, father.children)
end
end
end

...this code is untested but it should work. If "container" has no
find() method, just use .each and break, instead.
Something cool you could use is throw. This is simple enough to not
need it but you could just excercise your ruby-fu:

def recursive_find(name, container)
container.each do |father|
if father.name == name
throw :found, father # The second parameter should be catch's
return value...
else
recursive_find(name, father.children)
end
end
end

def weird_find(name, container)
catch :found { recursive_find(name, container) }
end

...this is also untested. catch returns a value, here, so weird_find()
will return what catch catches...
Good luck with your problem...

 

[Just Another Victim of the Ambient Morality]

I don't understand, exactly, what you're doing but there are some
things that are obviously wrong with your code and some techniques you
should probably know to implement what you're doing.
First of all, have you tested your own code? Your find() method
doesn't even store the value of its recursive call. It might still work
if that recursive call is the last thing your method does but you
explicitly evaluate the variable "found," ensuring that the recursed value
is never returned since it can never be the last thing done.
Secondly, using literal for loops is very pythonic and, thus, un-ruby
like. Wouldn't you rather where.each through elements?
Finally, there are many different ways to solve your problem. If where
is enumerable, you can use the find method:

def weird_find(name, container)
container.find do |father|
if father.name == name
father # Is this what you're looking for?
else
weird_find(name, father.children)
end
end
end

Actually, I was hitting the crack pipe pretty hard when I wrote this bit
with find(). It doesn't do what I thought it did.
You'll just need to use each with break...

def weird_find(name, container)
container.each do |father|
if father.name == name
found = father # Is this still what you're looking for?
break
else
found = weird_find(name, container)
break if found
end
end
found
end

...this is untested but should work...

 

[Alvaro Perez]

That last works fine. The problem is that I need an instance variable
@found reset to nil every time I start a new search (which I think is
not very elegant). But it works thought.

Thank you all!!!

 

[Just Another Victim of the Ambient Morality]

That last works fine. The problem is that I need an instance variable
@found reset to nil every time I start a new search (which I think is
not very elegant). But it works thought.

Which "last" was that?
I'm glad you've solved your problem. I'm a little concerned with your
confessed use of "instance variable @found." Why is "found" an instance
variable? It should probably be a local variable and, thus, you'd never
have to worry about "resetting" it every time...

 

[Alvaro Perez]

It's the only way that works so far. I need to explore inside the
children and break when I found the correct item or return nil. If it
were a local variable, when I break the loop it continues on the next
level of the tree (and then it would always return nil).

 

[Just Another Victim of the Ambient Morality]

It's the only way that works so far. I need to explore inside the
children and break when I found the correct item or return nil. If it
were a local variable, when I break the loop it continues on the next
level of the tree (and then it would always return nil).

Did my examples not work at all? I thought that, at worst, they'd have
some bugs that would be easily ironed out...
My throw example, if throw works the way I think it does, definitely
doesn't continue the recursion. Throw is the non-exception exception.
My non-throw exception should also cease the recursion, without the need
for a non-stack variable. The recursive function examines the return value
of the recursive call, ceases the search if something is found and passes
this back down the stack. That's all you have to do to cease the search:
pass the found item from one recursive call to the other. This unrolls the
stack just as an exception would. Does this really not work?