【算法】递归

一.基本概念

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<int>& a, vector<int>& b, vector<int>& c) {
        recursion(a,b,c,a.size());
    }

    void recursion(vector<int>& a, vector<int>& b, vector<int>& 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<0?1.0/pow(x,-(long long)n):pow(x,n);
    }

    double pow(double x,long long n)
    {
        if(n==0)
            return 1;
        double tmp=pow(x,n/2);
        return n%2==0?tmp*tmp:tmp*tmp*x;
    }
};