【递归、搜索与回溯】递归算法

一、经验总结

递归 VS 迭代（循环）

递归和迭代都解决的是重复的子问题，因此两者是可以相互转化的。利用栈结构可以将递归算法转化为迭代算法。

递归和迭代各有其优缺点，选择时需根据具体场景和需求来决定。

• 递归的优点包括：

  1. 简化问题：将大问题转化为小问题，减少代码量，使代码更简洁清晰，可读性更好。
  2. 有限语句定义无限集合：使用有限的循环语句实现无限集合的表示。
  3. 代码可读性好：递归代码通常更易于理解和维护。

  递归的缺点包括：

  1. 空间消耗大：递归调用会占用额外的栈空间，可能导致堆栈溢出。
  2. 效率较低：递归调用比迭代有更多的函数调用开销，可能影响运行效率。
  3. 需要设置结束条件：递归需要明确设置结束条件，否则可能导致无限递归至程序崩溃。

• 迭代的优点包括：

  1. 高效率：迭代算法的效率较高，运行时间只随循环次数增加而增加，没有额外的空间开销。
  2. 空间效率高：迭代算法在空间上更为高效，没有递归的额外栈空间消耗。

  迭代的缺点包括：

  1. 代码不如递归简洁：迭代算法的代码可能不如递归算法简洁。
  2. 编写复杂问题时困难：迭代算法在处理复杂问题时可能不如递归算法直观和易于理解。

综上所述，递归和迭代都可以有效地解决问题，但选择哪种方法取决于问题的性质、代码的可读性和维护性要求以及运行时的性能需求。在实际应用中，大多数情况下迭代的效率更高，但递归在某些情况下提供了更简洁、更易于理解的解决方案。

递归 VS DFS

递归算法其实就是对递归决策树进行一次深度优先遍历(DFS)，因此递归就是DFS。

二、相关编程题

2.1 汉诺塔

题目链接

面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）

题目描述

算法原理

编写代码

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        _hanota(A, B, C, A.size());
    }

    void _hanota(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {
        if(n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return; //记得return
        }

        _hanota(A, C, B, n-1);
        C.push_back(A.back()); //这里不能写A[0]
        A.pop_back();
        _hanota(B, A, C, n-1);
    }
};

2.2 合并两个有序链表

题目链接

21. 合并两个有序链表 - 力扣（LeetCode）

题目描述

算法原理

编写代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;

        if(list1->val > list2->val)
            swap(list1, list2);

        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
};

2.3 反转链表

题目链接

206. 反转链表 - 力扣（LeetCode）

题目描述

算法原理

编写代码

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

2.4 两两交换链表中的节点

题目链接

24. 两两交换链表中的节点 - 力扣（LeetCode）

题目描述

算法原理

编写代码

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

2.5 快速幂

题目链接

50. Pow(x, n) - 力扣（LeetCode）

题目描述

算法原理

编写代码

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