Most of the answers here are wrong. The right answer is it depends. For example, here are two C functions which walks through a tree. First the recursive one:
static
void mm_scan_black(mm_rc *m, ptr p) {
SET_COL(p, COL_BLACK);
P_FOR_EACH_CHILD(p, {
INC_RC(p_child);
if (GET_COL(p_child) != COL_BLACK) {
mm_scan_black(m, p_child);
}
});
}
And here is the same function implemented using iteration:
static
void mm_scan_black(mm_rc *m, ptr p) {
stack *st = m->black_stack;
SET_COL(p, COL_BLACK);
st_push(st, p);
while (st->used != 0) {
p = st_pop(st);
P_FOR_EACH_CHILD(p, {
INC_RC(p_child);
if (GET_COL(p_child) != COL_BLACK) {
SET_COL(p_child, COL_BLACK);
st_push(st, p_child);
}
});
}
}
It's not important to understand the details of the code. Just that p
are nodes and that P_FOR_EACH_CHILD
does the walking. In the iterative version we need an explicit stack st
onto which nodes are pushed and then popped and manipulated.
The recursive function runs much faster than the iterative one. The reason is because in the latter, for each item, a CALL
to the function st_push
is needed and then another to st_pop
.
In the former, you only have the recursive CALL
for each node.
Plus, accessing variables on the callstack is incredibly fast. It means you are reading from memory which is likely to always be in the innermost cache. An explicit stack, on the other hand, has to be backed by malloc
:ed memory from the heap which is much slower to access.
With careful optimization, such as inlining st_push
and st_pop
, I can reach roughly parity with the recursive approach. But at least on my computer, the cost of accessing heap memory is bigger than the cost of the recursive call.
But this discussion is mostly moot because recursive tree walking is incorrect. If you have a large enough tree, you will run out of callstack space which is why an iterative algorithm must be used.