If you're seeing this message, it means we're having trouble loading external resources on our website.

如果你被网页过滤器挡住,请确保域名*.kastatic.org*.kasandbox.org 没有被阻止.

主要内容

递归阶乘

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

本内容是 达特茅斯计算机科学 教授 Thomas CormenDevin Balkcom,与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA

想加入讨论吗?

尚无帖子。
你会英语吗?单击此处查看更多可汗学院英文版的讨论.