Break a recursive loop

Ruby
1

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!!

2

Alle lunedì 19 novembre 2007, Alvaro P. ha scritto:

     else

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 = if father == 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
Kernel#throw and Kernel#catch.

I hope this helps

Stefano

3

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.

2007/11/19, Alvaro P. [email protected]:

4

Steve Pugh wrote:

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…

5

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

_Steve

6

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

2007/11/19, Alvaro P. [email protected]:

7

“Just Another Victim of the Ambient M.” [email protected]
wrote
in message news:[email protected]…

    if (father.name==name) then

to find an object with the same name and return in, otherwise nil.
doesn’t even store the value of its recursive call. It might still work
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...
8

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!!!

9

“Alvaro P.” [email protected] wrote in message
news:[email protected]…

    else

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…

10

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).

11

“Alvaro P.” [email protected] wrote in message
news:[email protected]…

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?

12

“Alvaro P.” [email protected] wrote in message
news:[email protected]…

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…

13

I have the same problem and the code works for you also does not seems
to work.

def self.get_course_to_be_deleted( courses, array_course_name )
course_to_be_deleted = nil
array_course_name.each do |course_name|
course = courses.detect{ |course| course.name == course_name }
course_names = array_course_name - [ course_name ]
if course_names.empty?
course_to_be_deleted = course
break
else
get_course_to_be_deleted( course.children, course_names ) if
course.present?
break if course_to_be_deleted
end
end
course_to_be_deleted
end

It continues to execute the loop and course_to_be_deleted is returned as
nil…any solutions?

14

Ideally for this you define a signature that contains a single element
of the hierarchy only - not a set.

There are basically two options:

  1. Use catch and throw. For that you need a separate method for the top
    level which contains the catch and a method that is invoked recursively
    and throws if the terminator is found.

def top_level(item)
catch :result do
recurs(item)
end
end

def recurs(item)
throw :result, item if whatever_condition(item)

item.children.each do |child|
recurs(child)
end

nil
end

  1. Just return the result up the call stack.

def recurs(item)
return item if whatever_condition(item)

item.children.each do |child|
found = recurs(child) and return found
end

nil
end

If you want a collection as argument:

def recurs(items)
items.each do |child|
return child if whatever_condition(child)
found = recurs(child.children) and return found
end

nil
end

I find this a tad ugly. Also, the tree traversal happens in a different
order.