when building a web spider, should you use recursion ?

Question

building a depth-first web spider, meaning it will visit all links on first page, and go to each link, and visit links on all second page...

should you use recursion ? i find this to be cpu intensive.

def recursion()

linkz_on_first_page.each do |link|

recursion(link)

end
end
recursion(firstpage)

Answer 1

Definitely not, you're going to run into problems very quickly because of the actual nature of the world wide web. The second you hit a site with a main navigation section, where each page links to each other page, you've entered an infinite loop.

You could keep track of which links you have handled, but even then, a recursive loop doesn't really fit the nature of the world wide web (although at first thought it seems to, the web is more of an actual "web" than a tree). You're better off finding all links on the current page and adding those links (if they don't already exist) to a central queue, and proceeding iteratively through the queue processing every link as you come to it (remember to keep track of links that you've finished processing, or you'll add them to the end of the queue again)

Answer 2

Recursion seems to be appropriate - until you think a bit more about it. In case you've got a page A containing a link to page B and page B containing a link to page A you're stuck in an endless cycle.

Recursion is not any more CPU intensive than doing it in a "normal" way. You have to ask yourself whether you need all the links or if it's suffice to only grab links down to a certain level. In the latter case this also solves your endless cycle problem.

If you need all links I would rather use a list of links in which each link is unique. Your program takes a link from the list and spiders this link. Once a new link is discovered you try to insert it into this list and so on.

Answer 3

It's not so much that recursion is CPU intensive (it's not really), but more that you'll blow up your call stack after a few thousand recursive calls - which you would easily hit writing a web spider running on the open internet.

Example:

def blow_stack(level=0)
  puts "at level #{level}"
  blow_stack(level+1)
end

Output of this on my Macbook pro:

irb(main):009:0> blow_stack
at level 0
at level 1
... (skip a bunch of output)
at level 6295
at level 6296
SystemStackError: stack level too deep
        from (irb):7:in `blow_stack'
        from (irb):7:in `blow_stack'
        from (irb):9
        from :0