[音乐播放] 

道格·劳埃德：你可能认为， 代码只是用来完成任务。 你写出来。 它做一些事情。 这几乎是它。 

你编译它。 运行该程序。 你是好去。 

但是，不管你信不信，如果 你的代码很长一段时间， 你居然不妨来看看 代码东西是美丽的。 它解决了在一个问题 一个非常有趣的方式， 或有只是一些真正 整齐的有关它的样子。 你可能会笑 我，但这是事实。 和递归是一种方式 排序得到这个想法 美丽的，优雅的外观的代码。 它解决的方式的问题， 很有意思，很容易想象， 而令人惊讶的短。 

该方法递归作品 是，递归函数 被定义为一个函数调用 本身作为其执行的一部分。 这似乎有些奇怪， 我们会看到一点点 关于如何工作的时刻。 但同样，这些 递归程序 会是如此优雅 因为他们会 解决这个问题，而无需 拥有所有这些功能 还是这些长循环。 你会看到，这些递归 程序要看看这么短。 他们真的会做 你的代码看起来很多更漂亮。 

我给你举个例子 这怎么看 递归过程可能被定义。 所以，如果你熟悉这个 从数学课很多年前， 有被称为东西 阶乘功能，这通常是 表示为一个感叹号，这 是指对所有的正整数。 和的方式使n 阶乘的计算方法 是你乘的是 小于的数字 或等于n together-- 所有的小于整数 或等于n在一起。 

因此，5阶乘是5倍 4次3次2次1。 和4因子的4倍 3次2次1等。 你的想法。 

作为程序员，我们不这样做 用N，感叹号。 因此，我们将定义的阶乘 功能实际上为n的。 我们将用阶乘创建 递归地解决的问题。 我想你可能会发现 这是一个很多更直观 吸引力比迭代 版本的这一点，这 我们还将看看在某一时刻。 

因此，这里有几个 facts--双关语intended-- 关于factorial--的 阶乘函数。 1的阶乘，正如我所说，是1。 2的阶乘是2倍1。 3的阶乘是3 次2次1，依此类推。 我们谈到了4,5了。 

但看这，是不是这样的吗？ 是不是阶乘的2只 2倍的1的阶乘？ 我的意思是，1的阶乘是1。 那么，为什么我们不能只是说， 自2阶乘是2倍1， 它实际上只是2倍 1阶乘？ 

然后扩展这一想法， 是不是3的阶乘 短短3倍2的阶乘？ 和4的阶乘的4倍 3，等等的阶乘？ 事实上，阶乘 任何数量可以只 如果我们表达一种 携带这一点，直到永远。 那种我们可以概括 阶乘问题 因为它的n倍 阶乘ñ减1。 它的n倍的产物 所有的数字比我少。 

这样的想法，这 问题的概括， 允许我们递归 定义阶乘函数。 当你定义一个函数 递归，有 两件事情，需要成为它的一部分。 你需要有一种叫 基本情况，其中，当你触发它， 将停止递归过程。 

否则，一个函数调用 itself--你可能imagine-- 可以永远持续下去。 函数调用函数 调用函数调用 该函数调用的函数。 如果你没有办法 停止它，你的程序 将得到有效卡住 在无限循环。 它会崩溃，最终， 因为它会耗尽内存。 但是，这是题外话。 

我们必须要阻止一些其他的方式 除了我们的程序崩溃的事情， 因为一个程序崩溃是 也许不漂亮或优雅。 因此，我们称之为基本情况。 这是一个简单的解决方案 到停止的问题 递归过程的发生。 所以这是的一部分 递归函数。 

第二部分是递归情况下。 而这正是递归 将实际发生。 这是其中 功能调用自身。 

它不会调用自身完全相同 以同样的方式，它被称为。 这将是一个轻微的变化 这使得该问题是 试图解决一个很小的有点小。 但一般通过降压 的解决本体溶液的 到不同的呼叫的路线。 

这些长相 像基本情况吗？ 这些看起来像一个 最简单的解决问题的方法？ 我们有一大堆的阶乘的， 我们可以继续 去on-- 6，7，8，9，10，等等。 

但这些貌似之一 良好的情况下是基本情况。 这是一个非常简单的解决方案。 我们并没有做什么特别的事情。 

1的阶乘是只有1。 我们没有做任何 乘法可言。 好像如果我们要 尝试和解决这个问题， 我们需要停止 递归的地方， 我们可能要停止 它，当我们得到1。 我们不希望在这之前停止。 

因此，如果我们定义 我们的阶乘函数， 这里有一个骨架 我们如何做到这一点。 我们需要在这两个things--堵塞 基本情况和递归情况下。 什么是基本情况？ 如果n等于1，返回1--这是 要解决一个非常简单的问题。 

1的阶乘是1。 这不是1次东西。 这只是1。 这是一个非常简单的事实。 因此，可以是我们的基本情况。 如果获得通过1到这个 功能，我们就返回1。 

什么是递归 情况大概是什么样子？ 对于每一个其他数 除了1，什么模式？ 那么，如果我们正在做 n的阶乘， 的n是n次的阶乘减1。 

如果我们采取的3阶乘， 它是3负1 3倍的阶乘， 或2。 所以，如果我们不 看着1，否则 返回n倍 阶乘ñ减1。 这是非常简单的。 

并且为了稍微具有 更清洁和更优雅的代码， 知道，如果我们有单行循环 或单行条件分支， 我们可以摆脱所有的 他们周围的花括号。 因此，我们可以巩固这种此。 这具有完全相同的 功能这一点。 

我只是收走了大 牙套，因为只有一行 里面的那些条件分支。 因此，这些行为相同。 如果n等于1，则返回1。 否则返回n次 Ñ​​减去1的阶乘。 因此，我们正在做的问题较小。 如果n开出5，我们要 返回的4 5倍的阶乘。 我们会在一分钟内看到，当我们谈论 关于另一个视频通话stack-- 我们谈论了哪里 致电stack--我们将学习 关于到底为什么这个过程的工作。 

但5阶乘时说： 返回阶乘的5倍4，和4 会说，好了，好了，回报 4倍3的阶乘。 正如你所看到的，我们是 那种接近1。 我们越来越近 接近这一基本情况。 

一旦我们打的基本情况， 以前的所有功能 有他们在寻找答案。 2阶乘是说回归 2倍的1的阶乘。 那么，1返回1阶乘。 因此呼吁阶乘 2可以返回2次1， 并给出了回阶乘 3，这是等待该结果。 

然后它可以计算 其结果，3次2是6， 并给它回到4的阶乘。 再次，我们有一个 视频的调用堆栈 其中这被示出一个小 不是我在说什么，现在更多。 但是，这是它。 这仅仅是解决 计算一个数的阶乘。 

它只有四行代码。 这很酷，不是吗？ 这是一种性感。 

如此一般，但不 总是，递归函数 可以替代在一个循环 非递归函数。 所以在这里，并排，是迭代 版本阶乘功能。 这两种计算 同样的事情。 

他们都计算n的阶乘。 版本在左边 使用递归来做到这一点。 该版本在右侧 使用迭代来做到这一点。 

而通知，我们要声明 一个变量的整数产品。 然后我们循环。 只要n是大于0，我们 保持该产品用n乘以 和递减ñ直到 我们计算该产品。 所以这两个函数，再次， 做同样的事情。 但他们不这样做的 方式完全相同。 

现在，有可能 有一个以上的基 情况下或多于一个的 递归情况下，根据 在你的函数试图做的。 您不必仅仅局限于 单个基案或单个递归 案例。 的东西这么一个例子 有多个基例 可能是this--的 斐波那契数列。 

您可能还记得 小学生时代 该斐波那契序列定义 像this--的第一个元素是0。 第二个要素是1。 这两项都只是定义。 

然后每隔一个元素被定义 当n减去1和n减去2的总和。 因此第三元件 将0加1是1。 然后将第四元件 将第二个元素，1， 加所述第三元件，1。 这将是2。 等等等等。 

所以在这种情况下，我们有两个基例。 如果n等于1，则返回0。 如果n等于2，则返回1。 否则，正的回报斐波那契 减1加N减2的斐波那契数。 

所以这是多个基地的情况。 那么多个递归情况？ 那么，有什么东西 叫考拉兹猜想。 我不会说， 你知道那是什么， 因为它实际上是我们最后的 问题对于该特定视频。 而这是我们的运动 一起工作的。 

因此，这里的什么 在Collat​​z猜想is-- 它适用于每一个正整数。 它推测，它的 总是可能得到回 1，如果你遵循这些步骤。 如果n为1，停止。 我们得回到1，如果n为1。 

否则，通过这个 过程中再次n个除以2。 看看你能回到1。 否则，如果n是奇数，经过 这个过程再次3N加1， 或3 n次加1。 所以在这里，我们有一个基本情况。 如果n等于1，停止。 我们没有做任何更多的递归。 

但是，我们有两个递归的情况下。 如果n为偶数，我们做一递归 情况下，调用n乘2分。 如果n是奇数，我们做了不同的 递归的情况下，3 n次加1。 

这样一来，目标这个视频 花一秒钟，暂停视频， 并尝试写 递归函数在Collat​​z 你传递一个值n，其中和 它计算多少步它 才能到达1，如果你从n个开始 你遵循这些台阶之上。 如果n是1，它采取0的步骤。 否则，它会 走一步加然而， 它需要在任N多的步骤 除以2，如果n是偶数，或3n的加1 如果n是奇数。 

现在，我已经把在屏幕上点击这里 一对夫妇测试你的东西， 你一对夫妇的测试用例，看 什么这些不同在Collat​​z号码， 而且插图 的步骤 需要通过这样你就可以走了 那种看到这个过程在行动。 因此，如果n是等于 1，N的在Collat​​z为​​0。 你不必做 什么要回1。 你已经在那里了。 

如果n是2，它需要 一个步骤去1。 你开始2。 井，2是不等于1。 因此，这将是一步到位 加上然而，许多步骤是 需要n个除以2。 

2除以2为1。 因此，需要一步加然而， 许多步骤需要1。 1采取零步骤。 

3，你可以看到，有 相当多的步骤，参与。 你从3。 然后你去 10，5，16，8,4，2，1。 这需要七个步骤要回1。 正如你所看到的，有一个 其他几个测试用例在这里 来测试你的程序。 如此反复，暂停视频。 我会去跳回到我们 什么样的实际过程是在这里， 这是什么猜想。 

看看你能不能找出 如何界定的n在Collat​​z 因此，它计算多少 步骤才能到达1。 所以希望，你已经暂停视频 你不只是在等我 给你答案在这里。 但如果你是，那么， 这里的答案呢。 

所以这里有一个可能的定义 的在Collat​​z功能。 如果n是我们的基础case-- 等于1，我们返回0。 它没有采取任何 步骤要回1。 

否则，我们有两个递归cases-- 一个用于偶数，一个用于奇。 我测试连号的方式 是检查是否N模2等于0。 这基本上是，再次， 问这个问题， 如果你还记得什么国防部is--如果我 除以n乘2有没有余数？ 这将是一个偶数。 

所以，如果n模2等于0 测试是这样一个偶数。 如果是的话，我想回到1， 因为这绝对是 走一步加在Collat​​z 不管数字是我的一半。 否则，我想返回1 在Collat​​z加3 n次加1。 这是其他 递归步骤我们 可以采取的计算 Collat​​z--的步数 它需要找回 到1给出一个数字。 所以希望，这个例子 给你一点点 的递归过程的味道。 我们希望，你觉得代码是 小实施更漂亮，如果 在一个优雅的，递归的方式。 但即使没有，递归是一种 真正强大的工具，不过。 所以这是绝对的东西 围绕让你的头， 因为你能够创建 使用递归很酷方案 否则可能是复杂的写 如果您使用的是循环和迭代。 我是道格·劳埃德。 这是CS50。