Iterative or Recursive for ANSI C functions?

Discussion in 'Mac Programming' started by MorphingDragon, Aug 1, 2011.

  1. MorphingDragon macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #1
    I'm modifying the Mini-XML library to become an optimized ANSI-C SVG parser that can output OpenGL or Direct3D commands. I'm just wondering in terms of speed and efficiency, which is better for traversing XML trees in C; Iterative or Recursive functions? I want to keep the parser as small as possible in memory as for my uses will be used in conjunction with a caching system.
     
  2. robbieduncan Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #2
    It's a difficult question with, potentially, no answer. A function using an internal loop will need variables to track state. It may be that you need to keep a queue or similar so you will be dynamically creating and freeing memory on the heap. The same function written recursuively may not need to worry about queue/vector style state tracking as each function call will have it's own variable scope. But this will be on the stack. In addition return addresses and so on have to be stored.

    So it depends whether you worry more about stack or heap space...
     
  3. MorphingDragon thread starter macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #3
    I would say I would have to worry about stack space more than heap space.

    SVG doesn't define a maximum height or maximum roots in the XML tree so the stack could grow rapidly if the tree is fully unpacked in memory. The SVG files won't be parsed in real-time also so I can be aggressive with heap usage.
     

Share This Page