>> ZAMYLA：为了了解 递归，你必须
先了解递归。
在程序设计方法有递归 你有自我指涉
的定义。
递归数据结构，例如， 是数据结构
包括自己 它们的定义。
但是今天，我们要集中 在递归函数。
>> 回想一下，函数需要的投入， 参数，并返回一个值作为其
表示为输出 此图在这里。
我们想想盒子作为身体 的功能，包含该组
该解释的说明 输入和提供输出。
以身体内部一探究竟 该功能可以显示来电
其它功能。
就拿这个简单的函数foo，即 采用单个字符串作为输入，并
打印多少个字母 该字符串了。
该函数strlen函数，字符串长度， 被调用时，它的输出是
所需调用的printf。
>> 现在，是什么让一个递归函数 特别的是，它调用自身。
我们可以代表这个递归 这个橙色箭头打电话
循环返回到自身。
但是，只有再次执行本身会 再拍递归调用，并
其它一个又一个。
但是递归函数 不可能是无限的。
他们必须以某种方式结束，或者你 程序将一直运行下去。
>> 因此，我们需要找到一种方法来打破 出了递归调用的。
我们称之为基本情况。
当满足基本情况的条件， 该函数返回而不进行
另一个递归调用。
借此功能，喜，一个void函数 接受一个int n作为输入。
基本情况是第一位的。
如果n小于零，打印和再见 返回对于所有其他情况下，
功能将打印喜和执行 递归调用。
另一个函数调用喜 一个递减的输入值。
>> 现在，即使我们打印嗨， 函数将不会终止，直到我们
返回它的返回类型， 在这种情况下无​​效。
因此，对每一个n比基本情况外， 这个函数喜将返回喜
的n减1。
由于该功能是无效的，虽然，我们 这里将没有明确的返回类型。
我们只需要执行该函数。
因此调用喜（3）将打印和喜 执行喜（2）执行喜（1）1
它执行喜（0），其中所述 基本情况的条件得到满足。
因此喜（0）打印再见和回报。
>> 确定。
所以，现在我们了解的基本知识 递归函数，它们需要
至少一种碱的情况下，以及一个 递归调用，让我们进入到一个
更有意义的例子。
一个不只是返回 无效不管。
>> 让我们来看看阶乘 最常用于操作
概率计算。
n个阶乘是每一个的产品 比正整数
和等于n。
所以阶乘五是5倍，4倍 3次2次1，得到120。
四阶乘是4倍3倍 2次1给24。
而同样的规则也适用 到任何正整数。
>> 那么我们如何可以写一个递归 函数，计算阶乘
一个数字？
好了，我们就需要确定双方的 基本情况和递归调用。
递归调用是相同的 对于除基地所有情况
情况下，这意味着我们将不得不 找到一个模式，这将赋予我们
期望的结果。
>> 对于这个例子，看看如何5的阶乘 涉及乘以4×3×2×1
而这非常相同的乘法 这里被发现，该
定义4的阶乘。
所以我们看到，5的阶乘是 仅5倍4的阶乘。
现在没有这种模式适用 到4的阶乘呢？
是。
我们看到，4的阶乘包含 乘法3次2次1，则
同样的定义为3的阶乘。
所以4因子等于4倍3 阶乘，等等等等我们
图案坚持，直到1阶乘，这 通过定义等于1。
>> 有没有其他积极 整数离开了。
所以，我们有图案 我们的递归调用。
的n的阶乘等于n倍 n的阶乘减去1。
而我们的基本情况？
这将只是我们的定义 1阶乘。
>> 所以，现在我们可以继续写作 为函数的代码。
对于基本情况，我们将有 条件n等于等于1，其中
我们将返回1。
然后移动到递归调用， 我们将返回n倍
n个阶乘减1。
>> 现在让我们来测试这个我们。
让我们尝试阶乘4。
根据我们的功能是相等的 到4倍阶乘（3）。
阶乘（3）等于 3次阶乘（2）。
阶乘（2）等于2倍 阶乘（1），它返回1。
阶乘（2）现在返回2次1，2。
阶乘（3）现在可以返回 3次2，6。
最后，阶乘（4） 返回4次6，24。
>> 如果你遇到任何困难 用递归调用，假装
该功能的工作原理了。
我的意思是，你应该 相信你的递归调用返回
正确的价值观。
举例来说，如果我知道， 阶乘（5）等于5倍
阶乘（4），我要相信 阶乘（4）会给我24。
把它看成是一个变量，如果你 会，因为如果你已经定义
阶乘（4）。
因此，对于任何阶乘（n）时，它的 n的产物和
以前的阶乘。
而这之前的阶乘 通过调用获得
n个阶乘减1。
>> 现在，看看你是否可以实现 递归函数自己。
加载你的终端，或run.cs50.net， 写一个函数sum
接受一个整数n，并返回 所有连续的正和
整数n到1。
我已经写了一些款项 值，以帮助您我们。
首先，弄清楚 基本情况的条件。
然后，看总和（5）。
你可以在条件表达出来 另一个总和？
现在，大约总和（4）？
你怎么能表达总和（4） 在另一个总和条款？
>> 一旦你有了总和（5）和金额（4） 以其他款项的条款，请参阅
如果你能找出一个 图案总和（N）。
如果没有，请尝试其他一些数字 并表达他们的款项
条款的另一个号码。
通过识别模式的离散 数字，你对你的方式来
识别模式对任意n。
>> 递归是一个非常强大的工具， 所以当然它不是局限于
数学函数。
递归可以非常有效地使用 当树木，例如处理。
检查出的树木短的 更彻底的审查，但现在
记得，二叉搜索树，在 特别地，由节点时，每个
一个值，两个节点的指针。
通常，这是由表示 有一条线指向父节点
给左子节点和一个 右边的子节点。
二进制搜索的结构 树很适合
以递归搜索。
递归调用或者通过在 左或右节点，但更
那树短。
>> 说你要执行一个操作 二叉树的每一个节点。
你将如何着手呢？
好吧，你可以写一个递归 函数来执行该操作
父节点上，使递归 调用相同的功能，
通过在左侧和 右子节点。
例如，这个函数foo，即 改变一个给定的节点的值和
所有的孩子1。
的空节点的原因基本情况 函数返回，表明
有没有任何节点 留在该子树。
>> 让我们通过它。
首先家长是13。
我们将该值更改为1，然后调用 我们在左边的功能以及
如权利。
该函数foo，被称为左 子树的第一个，因此左节点
将被重新分配给1和foo会 被称为该节点的子节点，
第一左，然后右侧 等等，等等。
并告诉他们，分支机构不具有 任何更多的孩子因此同样的过程
将继续为儿童权利 直到整棵树的节点
重新分配到1。
>> 正如你所看到的，你不局限于 到只有一个递归调用。
正如许多如将完成这项工作。
如果你有一棵树，每个 节点有三个孩子，
左，中，右？
你会如何​​编辑富？
好了，简单。
只需添加另一个递归调用和 通过在中间节点指针。
>> 递归是非常强大的，而不是 提到优雅，但它可以是一个
难以理解的概念在第一，所以要 耐心，慢慢来。
从基础案例。
它通常是最容易识别， 然后就可以正常工作
向后从那里。
你知道你需要达到你的 基本情况，这样有可能
给你一些提示。
尝试在表达一种特定的情况下， 其他情况下，还是在子集。
>> 感谢收看这短暂的。
最起码，现在你可以 这样理解的笑话。
我的名字是Zamyla，这是CS50。
>> 借此功能，喜，一 空函数，它接受
一个int n作为输入。
基本情况是第一位的。
如果n小于0时，打印 “再见”和回报。