1、递归原理

函数调用自身。实质是函数每次调用自身时，都把一个问题分解为子问题。然后我们通过子问题的解，向上去构造大问题的解。

为了确保递归函数不会导致无限循环，它应具有以下属性：
一个简单的基本案例（basic case） —— 能够不使用递归来产生答案的终止方案。
一组规则，也称作递推关系（recurrence relation），可将所有其他情况拆分到基本案例。

2、递归函数

每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归就可以解决的地步。
递归分为三个步骤：
1、结束条件（Base case）
也就是递归的终点，可以直接得到结果，不需要进一步的递归调用就可以直接计算答案的情况。没有结束条件，递归就会形成死循环。有时，基本案例也被称为 bottom cases。
2、拆解
将问题拆解为小问题。
3、组合
通过递推关系式，将小问题构造为大问题。
例题：反转链表

迭代法：
三个指针：pre,cur,next

• next先保存cur的下一个节点
• cur->next再指向pre
• pre=cur
• cur=next;
  时间复杂度：O(n)，空间复杂度：O(1)

递归法：
假设除了头结点，其他节点都已经被反转。如何反转头结点与后面的链表？

• 首先我们从后往前进行反转
• 后面的节点指向前一个节点：head->next->next=head;
• 前一个节点不能指向后一个节点：head->next=nullptr;
  时间复杂度：O(n)，空间复杂度：O(n)

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

3、记忆化

递归算法中存在重复计算问题。每一次递归都要从头开始。可以借助外部存储，将已经便利过的节点值存下来，在递归中先判断该点是否存储过。最后，将计算得到的值再进行存储。
例题：斐波那契数列\爬楼梯
（1）递归。时间复杂度：O(2^n)。树形递归的大小为 2^n 。空间复杂度：O(n)。递归树的深度可以达到 n 。
（2）记忆化递归。时间复杂度：O(n)。空间复杂度：O(n)。
（3）动态规划。时间复杂度：O(n)。空间复杂度：O(1)。

4、时间复杂度和空间复杂度

我自己的理解是：时间复杂度是语句最多执行的次数。空间复杂度是存储变量所需要的最大空间。
例如，把结构中的每个变量遍历一遍，时间复杂度是O(n)。把它们全保存到数组，空间复杂度是O(n)。
时间复杂度：随着自变量的增长，算法所需时间的增长情况。 空间复杂度是指：
算法运行期间所需占用的所有内存空间

5、尾递归

尾递归函数是递归函数的一种，其中递归调用是递归函数中的最后一条指令。并且在函数中应该只有一次递归调用。
尾递归的特点就是我们可以很容易的把它转成 迭代（iterative ）的写法，当然有些智能的编译器会自动帮我们做了（不是说显性的转化，而是在运行时按照 iterative 的方式去运行，实际消耗的空间是 O(1)）
尾递归的好处是，它可以避免递归调用期间栈空间开销的累积，因为系统可以为每个递归调用重用栈中的固定空间。
为什么呢？是因为在尾递归的情况下，一旦从递归调用返回，我们也会立即返回，因此我们可以跳过整个递归调用返回链，直接返回到原始调用方。这意味着我们根本不需要所有递归调用的调用栈，这为我们节省了空间。
》 参考文献：这才是面试官想听的：详解「递归」正确的打开方式