我来晒道有深度的面试题！盛大的

Question

上半年面试盛大的一道面试题，心存疑惑，不是笔试，是CTO面试时问的，题目大意如下
用递归遍历1亿个节点（或无限个，意识是足够大的）的二叉树，会不会有问题？
因为是口述的，后面做了些说明，可以不考虑这些节点所占的空间，题目主要问递归这一块，其实就是内存
在他的提示下，我算了回答正确了，大致是，递归函数体是存在堆上的，而递归调用时，在栈上存放函数地址，由于要遍历一亿个节点，也就是要存放一亿个函数指针，会把栈爆掉！他的意思也是这个意思！
但我回来后网上查了下，.net实现递归的方式好像是用栈（stack,先入后出）来实现的（递归可以用栈实现的，代码网上找去），如果这样的话，这个stack最大的长度只可能是二叉树的深度！也就是，不可能出现一亿个函数指针同时出现在栈上（内存中堆栈的栈），所以栈是不会爆掉的！
由于数据量太大，不容易验证！有清楚的来讨论下！

Answer 1

void Visit(Node node)
{
   if( node.IsLeaf() )
   {
       node.Print();
   }
   else
   {
       Visit( node.LeftChild );
       Visit( node.RightChild );
   }
}1                *
2        *               *
3    *       *       *       *
4  *   *   *   *   *   *   *   *
5 * * * * * * * * * * * * * * * *
上面是递归遍历的伪代码，我们可以看到递归的深度就是到达叶节点的深度。n层的完全二叉树可以存放2^n-1个节点。
1亿个节点只要ceiling( ln(10000*10000) )=19层就放的下了，递归遍历的深度也就是19。也就是说1亿亿个节点，也只要37层左右，递归本身也不会有问题。当然要假设这里的二叉树是指完全二叉树。

Answer 2

如若按照stack的算法，也是这个结果，所占空间就是树的深度！
谁能说说.net的递归内部实现啊

Answer 3

如果不是完全二叉树，是会退化，但不一定是另外一个数量级。
平衡树（红黑树，AVL树等）的深度也是Log(N)级别的。二叉树实际实现大部分都是平衡树，或接近平衡树的搜索效率。

Answer 4

错了，
应该是Log以2为底的1亿，等于26点多层，ln是e为底的指数
这个递归最大的问题，主要在数据项的大小会超过，机器的内存，可能需要，这会导致处理过程中，需要将一些数据，存储到硬盘中。在需要用到的时候，再取来了

Answer 5

我现在也碰见一个类似的问题，
5位的随机数向数据库中添加，如果数据库中有就在次执行本函数，
没有就加入到数据库中，
执行到6千多的时候，就报错了，大概意思就是堆栈溢出了，
大概的代码就是
public void zj()
{
int count=selece count(*)....;//查询是否有
   if(count>0)
   {
     zj();
   }
   else
  {
   add...//加入数据库
  }
}

Answer 6

tai shen le bu dong a !!

Answer 7

内核模式下必挂,ring3应该也差不多.