>> [音乐播放]
>> 道格·劳埃德：你可能认为， 代码只是用来完成任务。
你写出来。
它做一些事情。
这几乎是它。
>> 你编译它。
运行该程序。
你是好去。
>> 但是，不管你信不信，如果 你的代码很长一段时间，
你居然不妨来看看 代码东西是美丽的。
它解决了在一个问题 一个非常有趣的方式，
或有只是一些真正 整齐的有关它的样子。
你可能会笑 我，但这是事实。
和递归是一种方式 排序得到这个想法
美丽的，优雅的外观的代码。
它解决的方式的问题， 很有意思，很容易想象，
而令人惊讶的短。
>> 该方法递归作品 是，递归函数
被定义为一个函数调用 本身作为其执行的一部分。
这似乎有些奇怪， 我们会看到一点点
关于如何工作的时刻。
但同样，这些 递归程序
会是如此优雅 因为他们会
解决这个问题，而无需 拥有所有这些功能
还是这些长循环。
你会看到，这些递归 程序要看看这么短。
他们真的会做 你的代码看起来很多更漂亮。
>> 我给你举个例子 这怎么看
递归过程可能被定义。
所以，如果你熟悉这个 从数学课很多年前，
有被称为东西 阶乘功能，这通常是
表示为一个感叹号，这 是指对所有的正整数。
和的方式使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。