BFS: recursive vs iterative

Question

Are there any advantages to writing a BFS tree-traversal algorithm recursively vs iteratively? It seems to me iterative is the way to go since it can be implemented in a simple loop:

1. Enqueue root node
2. Dequeue node and examine
3. Enqueue its children
4. Go to step 2

Is there any advantage to recursion? It seems more complex with no advantages.

Thanks in advance...

Answer 1

When considering algorithms, we mainly consider time complexity and space complexity. The time complexity of iterative BFS is O(|V|+|E|), where |V| is the number of vertices and |E| is the number of edges in the graph. So does recursive BFS. And the space complexity of iterative BFS is O(|V|). So does recursive BFS.

From the perspective of time complexity and space complexity, there is no difference between these two algorithms. Since iterative BFS is easy to understand, it is not surprising that people prefer iterative BFS.