@Golevka 大哥，我觉得你混淆了好多情况啊。。：
1、时间复杂度：一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，是对一个算法在运行过程中临时占用存储空间大小的量度； 递归算法在结束全所有节点都不得释放，O(logN)能存的下O（N）级的内容？ 不论是啥样的dfs算法，需要的空间起码是O（n）的，因为是遍历n个节点，起码记录节点遍历没有的标记符就要有N个； O(logN)那是完全二叉树的高度，是完全二叉树的递归层数，可以说是一个特例而已，也只能说是和空间相关。

2、dfs的遍历方式是给定的，只要照着dfs做，除非故意找茬（故意开个超大内存啥的），算法的空间时间复杂度都是一样；

3、栈空间和内存空间不是一回事，vc6的C语言编译器默认的栈空间只有1M(其他环境相差不大，反正默认的都不大)，不然大家怎么会天天说递归容易爆栈？想要扩大栈空间只有在程序运行前在IDE或是命令行里指定，就是说程序本身决定不了，这样的递归，除非你每次运行前都先估摸这一下要用多少栈空间，不然应付各种规模数据的时候总会有爆掉的一天；相比来说，可以在内村里手动开辟的法子显然更好；

4、有一个很重要的问题，我再重复一下，dfs的空间、时间复杂度，在算法上是一样的，不是说递归层数变少，空间就变小了；层数变少，只是要存的局部变量就是变少了，但是用其他方法实现的时候完全可以不存储那些局部变量：
int a(){
int b;
if xx:
return;
a();
}
b要存下；

while(!xxx){
int b
&(&(
}
b不用存；

因此，在理论上时间，空间一致的情况下，递归还有各种实现上的开销，所以效率低；

PS：这句话：“都会先开一个容器(数组，字典都行)，把所有节点的初始状态保存进去”，存的就是二叉树好吧，二叉树经常这么存储，然后在每个节点元素里加上个种信息。
本来还想在写点，但是看着已经写好多了，在写下去就太烦了。。，主要是觉得你没搞懂。。。还说我的法子不对。。有些不爽。。