主要内容
递归阶乘
对于正值 ,, 让我们写 , 因为我们以前做的, 作为一个乘积的数字从 开始, 并下降到 1: = .但请注意, 是 的另一种写作方式, 所以我们可以说, . 你看到我们刚才做了什么吗?我们写了 作为一个乘积, 其中一个因素是 .我们说你可以计算 通过 ,然后乘以计算 的结果 . 你可以计算 的阶乘函数, 首先计算阶乘函数在 . 上. 我们说计算 是一个子问题, 我们解决计算 !.
让我们看一个例子: 计算5!
- 你可以用
计算 5!。 - 现在你需要解决计算 4!的子问题, 你可以计算为
!. - 现在你需要解决计算3!的子问题 , 也就是
. - 现在 2!, 也就是
. - 现在你需要计算 1!. 你可以这样理解 1! 等于 1, 因为它是从1到1的所有整数的乘积。或者你可以应用这个公式
. 让我们通过应用公式来做到这一点. - 我们定义 0! 等于 1.
- 现在你可以计算
. - 通过计算
, 你可以计算 . - 通过计算
, 你可以计算 . - 通过计算
, 你可以计算 . - 最终, 通过计算
, 你可以通过计算完成 .
所以现在我们有了另一种思考如何计算 的值的方法, 对于所有非负整数 :
- 如果
, 声明 . - 否则,
必须为正数。 解决计算的子问题 , 将此结果乘以 , 并声明 等于此乘积的结果。
当我们计算 以这种方式, 我们调用第一个情况, 我们立即知道答案, 基本情况 , 我们调用第二个情况,我们必须在不同的值的情况下计算相同的函数, 递归情况 。