Recursion Speed vs Single Function

General
1

Hi all

I’m working on a little HTML parser which loads a page into a hierarchical structure of HTMLNode objects. My current approach uses a recursive method which steps down into each node and my 24.5KB test file is parsing in ~64 msec in the IDE.

I’m now looking at ways to improve the speed where possible and I wanted to check that recursion is still an appropriate choice here given a couple of issues I have:

  1. Theoretically, with a html structure many levels deep, I could run out of stack space during the processing. Although I haven’t encountered this situation yet so not sure how likely this is?
  2. I imagine that there must be a time penalty each time another function is called? If I’m processing hundreds or thousands of objects via recursion, does it not reach a point where the time taken to call the function multiple times outweighs performing all the processing in a single function call? How significant is this?

If anyone could offer any advice/tips in this regard that would be much appreciated

2

You’d have to benchmark, but I have seen dramatic performance improvements by eliminating method calls, including recursion. Use arrays as stacks in a loop, and you will probably see the same.

(Assuming every ms counts, that is. Take a look at my M_Crypto module for examples of fast code that uses this advice but is a nightmare to read and maintain.)

1 Like