算法专题十一： 基础递归

1. 汉诺塔

题目链接： Leetcode汉诺塔

算法原理：

递归：宏观视角理解递归
本道题为什么能用递归？ 让我们逐一分析
首先思考我们如何来解决汉诺塔问题：

1. 当N = 1 时， 我们仅需将A上的盘子直接挪到C即可

2. 当N = 2时， 把A上的盘子转移到B上，再把A的最后一个盘子转移到C上，最后再把B上的盘子转移到C上。

3. 当N = 3时跟N = 2的思路一样， 先把B上的n-1个盘子转移到B上（借助C）,再把A上的最后一个盘子转移到C上， 最后将B上的盘子转移到C上（借助A）,

4. 当N = 4时，

解决大问题时具有相同的子问题时，解决子问题又出现相同类型的子问题时就可以使用递归。
根据重复的子问题，设计函数头
只根据某一个具体的子问题在做什么，设计函数体

编写代码：

class Solution {
public:
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
        int n = a.size();
        dfs(a, b, c, n);
    }
    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
    {
    //递归出口，当n == 1时就可以直接转移，无需借助其他柱子
        if(n == 1) 
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        //第一步
        dfs(a, c, b, n - 1);
        //第二步
        c.push_back(a.back());
        a.pop_back();
        //第三步
        dfs(b, a, c, n - 1);
    }
};

2. 合并两个有序链表

题目链接：合并两个有序链表

算法原理：

先比大小，让小的那个节点连上后面合并好的链表。

/**
 * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;
        if(l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

3. 反转链表

算法原理：

从宏观角度看待问题：

1. 让当前节点后面的节点先逆置， 并且把新的头节点返回
2. 让当前节点添加到新的节点后面即可。

边界情况：
当链表为空或者只有一个节点， 返回当前节点即可，即为递归出口。

编写代码：

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

4. 两两交换链表中的节点

题目链接： 两两交换链表中的节点

算法原理：

1. 先将当前两个节点之后的节点进行交换， 然后在交换当前节点
2. 如果当前节点为空或者只有一个节点就不用交换了， 直接返回即可
3. 让当前节点的下一个节点的next指向当前节点， 并且让当前节点指向tmp即上一层已经交换好的链表，并且返回当前节点的下一个节点。

编写代码：

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

5. Pow(x, n)

题目链接： Pow(x, n)

算法原理：这个就是求x的n次方， 如果使用暴力解法， 当n特别大时是会超时的， ，那么我们采用第二种思路， 递归的思想

1. 如果求3的16次方， 我们可以先算出3的8次方*3的8次方， 按照下面的图进行求解
2. 求解子问题设计函数头 就转化为定义一个函数， 你给我返回它的一半的值，
   如果是奇数就再乘以当前的数， 如果是偶数就直接tmp*tmp即为结果
3. 递归的出口就是当n == 0时， 返回1即可。注意处理负数的情况。
   

编写代码：

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

完