其实，很多数据结构的题都很适合用递归算法来解：如链表，如树，还有一些查找也非常适合递归，如二分查找，如归并，如堆查找。

但是递归函数不好写啊，一点小漏洞，都会让你改起来痛苦的不行不行的。其实理解一下，递归函数就是同一个模子，给不同的东西做操作。

一个含直接或间接调用本函数语句的函数被称之为递归函数，在上面的例子中能够看出，它必须满足以下两个条件：1） 在每一次调用自己时，必须是（在某种意义上）更接近于解；2） 必须有一个终止处理或计算的准则。

　　对于（1）我的理解就是，自己调用自己的时候，参数要变，这个参数的改变，让此次操作更接近底层，一直到底层后，会有终点返回，然后一层层返回。

来点题吧，干巴巴说没意思。

1.两个有序链表的合并：

红色部分就是以上所说的，出口处理，以及参数变化。

ListNode* Merge(ListNode* L1, ListNode*L2)  {    if(L1 == NULL)        return L1;    if(L2 == NULL)        return L2;    ListNode* newhead = NULL;    if(L1->value
      
       value)    {        newhead = L1;        newhead->next = Merge(L1->next,L2);    }    else    {        newhead = L2;        newhead->next = Merge(L1,L2->next);    }        return newhead;}
      

2.二叉树的反转

 

/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(x), left(NULL), right(NULL) {    }};*/class Solution {public:    void Mirror(TreeNode *pRoot) {        if(pRoot==NULL)            return;        if(pRoot->left==NULL&&pRoot->right==NULL)        {            return;        }        if(pRoot->left&&pRoot->right)        {            TreeNode* tmp = pRoot->right;            pRoot->right = pRoot->left;            pRoot->left = tmp;        }        else if(pRoot->left&&!pRoot->right)        {            pRoot->right = pRoot->left;            pRoot->left = NULL;        }        else if(pRoot->right&&!pRoot->left)        {            pRoot->left = pRoot->right;            pRoot->right = NULL;        }        Mirror(pRoot->right);        Mirror(pRoot->left);    }};