自己调用自己的算法——递归算法

我们看下面这个图片，里面是1个盘子，2个盘子和3个盘子的情况。当只有一个盘子的时候我们只需要把A上面的这个盘子给放到C上。当是2个盘子的时候，我们先借助C把盘子给到B上，接着把A上面最大的那个盘子给C，接着用同样的方法把B盘子中最大的那个给C，循环往复。当是3个盘子时也是同样的方法。然后我们就发现了这个重复子问题，就是不断的通过借助中间柱子把盘子给放到C上面。

那我们的出口是什么呢？出口就是当A或者B上面只有一个盘子的时候我们就该结束了，直接把最后一个盘子给放到C上面，接着直接return。

我们看下面这个代码，dfs这个函数头表示X借助Y的帮助把盘子放到Z上。按照前面所说的，我们先借助Z把X上面的n-1个盘子给转移到B上，接着把X上面的那个盘子给放到Z上。接着借助X把Y上面的盘子给转移到Z上面。

PS：我们这边要注意，就是递归的出口基本上是写在最前面的，这样才可以防止死循环。

class Solution { public: void dfs(vector<int>& x, vector<int>& y, vector<int>& z,int n) { if(n==1) { z.push_back(x.back()); x.pop_back(); return; } dfs(x,z,y,n-1); z.push_back(x.back()); x.pop_back(); dfs(y,x,z,n-1); } void hanota(vector<int>& a, vector<int>& b, vector<int>& c) { dfs(a,b,c,a.size()); } };

2.2 LeetCode21. 合并两个有序链表

我们接下来看下面这道题，这道题的题目很简单，就是要求我们把下面两个链表给合并成一个链表。注意在这道题中我们不可以再生成一个链表。

这道题我们直接看代码，我们直接在题目给的函数里面进行递归，首先这个函数的函数头就是合并链表，出口就是但我们一个链表为空的时候直接返回另一个链表。

接着我们就开始判断两个链表里面的值，小的那个放到前面，接着再进行递归。因为我们前面说过了，这个函数头表示的是合并链表，我们我们直接当前节点的next=它就好了，代码会自己递归下去的。

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(!l1) return l2; if(!l2) return l1; if(l1->val<=l2->val) { l1->next=mergeTwoLists(l1->next,l2); return l1; } else { l2->next=mergeTwoLists(l1,l2->next); return l2; } } };

2.3 LeetCode206. 反转链表

我们看下面这道题，题目就是要求我们翻转链表。

前面忘记说了，就是一道题的话并不是唯一解法的，像这道题我们既可以用递归，也可以使用一个三指针。

我们看下面这个代码dfs这个函数头表示的是当前需要进行反转的节点，接着出口就是当我们遇到最后节点或者空节点的时候进行return。

其中因为是单链表，所以我们在这里需要提前保存最后一个节点的位置，也就是这里面的newnode。接着的话就是叫当前节点的后一个节点指向当前节点，然后当前节点指向空（在这里直接指向空不会干扰到前面的节点，因为递归的过程中间已经记录下了上一层节点了）。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* dfs(ListNode* l1) { if(!l1||!l1->next) { return l1; } ListNode* newnode=dfs(l1->next); l1->next->next=l1; l1->next=nullptr; return newnode; } ListNode* reverseList(ListNode* head) { return dfs(head); } };

2.4 LeetCode50. Pow(x, n)

我们看下面这道题，就是叫我们手动实现一个pow函数。接着我们发现在这道题里面，n即可以能是一个负数，也可能是一个很大的数，所以我们在设计代码的时候要注意。

我们看下面这个图，下面这个就是我们发现重复子问题的过程，2的16次方可以通过两个2的8次方相乘来实现，2的8次方可以通过两个2的4次方相乘来实现。这样我们就发现了重复子问题。我们的递归也就按照它来进行设计。

我们看下面这个代码，首先名为要给m赋值给一个long long类型的值，因为m会很大。同时我们要注意这个m是可以为负数的，所以在这里如果为负数的话我们就要把x=1/x;接着把转换成正数（这一步我们是把负数的那个负号提前给x）。接着我们就按照上面所说的方式来实现递归，代码从下往上一点点走，下面那个ifelse判断就是判断有没有走到最后，也就是上面图片里面的1X2这一步。

class Solution { public: double myPow(double x, int m) { long long n=m; if(n<0) { x=1/x; n=-n; } if(n==0) return 1.0; double tmp=myPow(x,n/2); if(n%2==0) { return tmp*tmp; } else return tmp*tmp*x; } };