Recursion

Recursion(递归)

简而言之就是自己运算自己

关键问题是:什么时候停止递归?

如果没有终止条件，递归会一直进行下去，导致栈溢出。所以，递归必须有终止条件。

---

递归和循环

递归和循环的区别在于：

• 递归是一种自上而下的计算方式，循环是一种自下而上的计算方式。
• 递归解决的问题一般都可以用循环来解决，但是循环解决不了的问题，这时候就需要用递归来解决。

例如：

计算机阶乘的两种实现方式：

• 递归：

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

• 循环：

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

递归的优点：

• 代码简单，容易理解。
• 递归可以解决很多问题，比如计算阶乘、计算二项式展开、计算组合数、计算汉诺塔、计算图的遍历等等。
• 递归可以代替循环，减少代码量。

递归的缺点：

• 递归调用栈的开销大，容易发生栈溢出。
• 递归容易陷入死循环。
• 递归代码的性能不一定比循环代码的性能好。

---

递归的应用

1.汉诺塔问题

汉诺塔问题是指将一堆盘子从左边移动到右边，又或者从右边移动到左边，最后移动到中间的过程。

汉诺塔问题的递归解法：

1. 将 n-1 个盘子从左边移动到右边，中间放置一个空盘子。
2. 将最底下的 n-1 个盘子从左边移动到中间。
3. 将 n-1 个盘子从右边移动到中间。
4. 将中间的空盘子放置在左边的最底下。

void hanoi(int n, char from, char to, char via) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    hanoi(n-1, from, via, to);
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hanoi(n-1, via, to, from);
}