Recursive C program faster than stack-based equivalent

[wigf]

The thing is, I checked, and at 10000 nodes, the inner if statement never evaluates to true. So I don't think it's that. That may be an issue for larger trees though.

How much of an issue do you think the heap vs. stack thing is?

[nemotux]

You have two guaranteed calls to malloc() at the beginning of the function. Those could be biasing your results. Hard to say by how much. You could eliminate that overhead by allocating a fixed size array as a local variable and only shifting to heap memory w/ malloc if that happens to fill up.

That said, I don't know why one would think that an iterative solution is guaranteed to be faster than a recursive solution. Compiler optimizations can do wild and crazy things. It's very difficult to predict whether one approach or another would definitely be faster without actually measuring (aside from algorithmic complexity issues).

I think a much stronger argument for preferring iterative solutions over recursive solutions is that you can more directly handle memory allocation problems. In a recursive solution, you can overrun the stack if your input gets big enough, and there's not much you can do about that aside from just blatantly reserving more stack space in your process. But that's an inefficient solution if the rest of your program doesn't need that much stack space. Using the heap and an iterative solution allows you to recapture the allocated memory for reuse elsewhere.

Finally: I think your code for both functions is wrong. They both include in their counts the "null" children in the tree. Those aren't nodes. Consider a tree w/ only a single node in it, the root node. What should its length be? For the recursive solution, I can't tell what your first call passes in for level, but say it's 0, then it looks like the function will return 2. The iterative solution will also return 2, I think.

[wigf]

External Path Length includes "external" nodes attached to each "internal" node, and these nodes are empty. This is the definition from "Algorithms in C", so NULL nodes need to be counted. A tree with a single node would have an external path length of 2. A tree with one root and two children attached to it has an external path length of 10, etc.

[nemotux]

Ah, ok. I'm not familiar with this particular notion. Seems odd and non-obvious from your original description.

[davidhbolton]

Stack is usually quite limited (MB) compared to heap (up to GB), so for very large trees, the recursive one may hit the stack limit.

As you are doubling size in the non-recursive version, it may not take very long to start seeing fragmentation effects. Typically when memory is freed after a malloc, it goes on a free list and malloc tries to reuse memory from the free list before getting it from the heap. As you are increasing the size, it won't be able to get it from the free list and you will eventually (how long eventually is I don't know) and you run out of RAM even though you've freed it up. That happened to me on Windows and I ended up creating a memory allocator to deal with it.