【算法】递归

一.基本概念

1.什么是递归？

���数自己调用自己，主问题由相同的子问题组成，子问题又由相同的子问题组成。

2.如何理解递归？

不要在意递归的细节展开图，把递归的函数当成一个黑盒，相信这个黑盒一定能完成这个任务。

eg:二叉树的遍历，归并排序，快排

3.方法论

1.先找到相同的子问题（确定函数头，参数返回类型）

2.只关心某一个子问题是怎么解决（确定主函数体）

3.确定函数终止条件（确定递归出口）

二.汉诺塔问题

思路：

两个盘子时，假设有a b c三个柱子，把a移到c，盘子设为1 2 从上到下升序排列。先把1移到辅助柱子b，再把2移到c，最后把1移到c。

三个盘子时，先处理上面两个，用同样的方法，假设从上到下123，目标是把12先移到b，把3移到c。先把1移到辅助柱子c，然后2移到b，c移到b，3移到c。再把1移到辅助柱子1,2移到3，1移到3.

可以看到当n个盘子时，n-1个盘子是它的子问题。

方法论

1.重复子问题：将a柱子上的几个盘子借助辅助柱子b放到另一根柱子c上，函数参数便可以得知a，b，c，n（几个盘子要转移）。recursion(a,b,c,n)

2.函数体实现：

step1.N=n时，先把a的n-1个盘子由辅助盘c转移到b

recursion(a,c,b,n-1)

step2.把a剩下的一个移到c

a.back()->c

step3.把b上的n-1个盘子借助辅助柱子a转移到c

recursion(b,a,c,n-1)

3.递归出口

n=1时，直接将a移到c

代码实现

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

三.链表

反转链表

思路1：从宏观角度看待

1.让当前节点后面的链表先逆置，并且把头结点返回。（相信你一定能完成）

2.让当前节点添加到逆置后的链表即可

思路2：将链表看成一棵树（后序遍历）

1.深度优先遍历一次即可

代码实现

class Solution {public:    ListNode* reverseList(ListNode* head)     {        if(head==nullptr||head->next==nullptr)            return head;        ListNode*newhead=reverseList(head->next);        head->next->next=head;        head->next=nullptr;        return newhead;    }};

两两交换链表中的节点

思路：宏观角度看问题

先交换前两个节点，然后连接后面剩下的节点，结束条件当为空或者后面无节点。

代码实现：

/** * 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* swapPairs(ListNode* head) {        if(head==nullptr)            return nullptr;        if(head->next==nullptr)            return head;        ListNode*newhead=head->next;        ListNode* tmp=head->next->next;        head->next->next=head;        head->next=swapPairs(tmp);        return newhead;    }};

快速幂

实现pow（x,n）

代码实现

class Solution {public:    double myPow(double x, int n) {        return n        if(n==0)            return 1;        double tmp=pow(x,n/2);        return n%2==0?tmp*tmp:tmp*tmp*x;    }};