理解递归，从递归的本质说起

遍历二叉树，是学习树这种数据结构首先要理解的一种基本操作。比较简单地方式就是用递归去遍历，鉴于递归这种调用方法有一定的特殊性，今天还是想来讲讲怎么去理解递归遍历。本文针对想理解递归的过程的朋友，因为本人在学到这一部分的时候也纠结了很久，其实只要理解了过程，那以后写递归的代码再也不用“心虚”了，因为那个过程是可预测的，可证明的。

递归调用的特殊性在于自己调用自己，给人一种迷茫感，如果是递归调用“一次”，那还相对好理解，比如求阶乘的递归算法，

  
  

    
    
    
    

     
     

      
      int F(int n)
     
     
    
    

    
    
    
    

     
     

      
      {
     
     
    
    

    
    
    
    

     
     
	
      
      if(n==
      
      0)
      
      //递归边界
     
     
    
    

    
    
    
    

     
     

      
                  
      
      return 
      
      1;
     
     
    
    

    
    
    
    

     
     
	
      
      return n*F(n
      
      -1);
      
      //递归公式
     
     
    
    

    
    
    
    

     
     

      
      }
     
     
    
    
  
  

一层一层调用，知道递归结束条件成立，再一层一层返回；但如果像二叉树是递归调用“两次”，似乎理解起来就不是很容易了。

  
  

    
    
    
    

     
     

      
      void preorder(bintree t){
     
     
    
    

    
    
    
    

     
     
    
      
      if(t){
     
     
    
    

    
    
    
    

     
     
        
      
      printf(
      
      "%c ",t->data);
     
     
    
    

    
    
    
    

     
     

      
              preorder(t->lchild);
     
     
    
    

    
    
    
    

     
     

      
              preorder(t->rchild);
     
     
    
    

    
    
    
    

     
     

      
          }
     
     
    
    

    
    
    
    

     
     

      
      }
     
     
    
    
  
  

对于一颗如下的二叉树，它的前序遍历顺序该怎么理解呢？我们今天来好好理一遍它的过程。

可以把递归看成是自己调用另一个和自己功能一样，但是函数名不同的函数来理解，或许看得更清楚明白，下面我们来看看这个前序遍历的过程是怎样的。

首先，我们记上面这个函数为F1，表示外层的函数，内层函数表示下一层的函数，也就是第二层的F2，依次类推。

那从F1依次调用直到F3，注意这个时候都是在左子树就是L的调用，所以依次打印出“A B D ”,这都没什么问题，就是普通函数调用。F3调用F4的时候，记得我们层函数的最前面是递归的退出条件，也就是空子树就返回，由于D的左子树是空，所以到这里F4会返回到F3，即返回到L之后，R之前。

接在，在F3层，从R开始继续调用F4，即开始访问D的右子树，此时打印出“F”，然后调用F4的左子树，也就是调用F5函数，当然是空，所以返回到F4,再调用F4的右子树，也是空，所以也是返回到F4，此时F4这一层已经全部调用完成，所以继续向上返回到F3，记得我们之前是怎么下来的吗，就是从F3的右子树开始访问，所以F3层函数也已经调用完成，继续往上返回到F2。

继续调用F2的右子树，也就是调用F3函数，此时打印出“E”，接着再访问E的左右子树，都是空，所以返回到F2，F2层函数已经全部调用完成。返回到F1，也就是A的左子树部分全部访问完成，此时开始访问A的右子树，打印出“C”，再推下去就是依次打印“G”和“H”。至此，整颗二叉树节点前序遍历完成，顺序就是“A B D F E C G H”。

二叉树是一种递归定义的数据结构，所以用递归来写它的相关算法是顺理成章的，只是有时候觉得需要稍微理解一下这个过程，这个就是我的理解方法。