APS105预习 - 09

前言

断了好几天，今天继续

Chapter 11 Recursion 递归

递归是一种分治思想的产物。分治，故名思义，先分后治，先将问题拆解成一个个元问题，然后想办法解决每一个微观上的小问题，从而最终解决宏观上的大问题。

递归首先要找到解决一个问题的较小实例，使用一个函数，反复调用自身，直到在最小的问题上找到解决方案。

11.1 递归的定义

阶乘

说到阶乘，我们很容易实现一个朴素的阶乘算法

int factorial(int n) {
  int fact = 1;

  for (int i = 1; i <= n; i++) {
    fact = fact * i;
  }

  return fact;
}

但是，如果应用分治的思想，很容易能发现：

n! = n * (n-1) * (n-2) * … * 1 = n * ! (n-1)

于是便可以得到如下算法：

int factorial(int n) {
  return n * factorial(n - 1);
}

如果实际运行，就会发现，该函数会一直运行，直到程序内存耗尽。所以……

⚠️递归函数一定要有终止条件！！！！

正确代码如下：

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

递归函数的必须组成部分有：

• Base case: 该问题的最小实例的解
• Recursive call: 在到达最小实例之前，如何拆分问题

Recursive function (problem)
    if terminating condition
        may do a simple calculation;
        return;
    else:
        break problem into a smaller piece/s
        Recursive function (smaller piece/s)