道格·劳埃德:如果你看过 视频上的递归, 整个过程可能 似乎有点不可思议。 它是如何工作的? 如何职能知道他们 需要等待,等待另一个值 从不同的功能回归 为了得到我们想要的结果打电话? 好了,这个工作的原因是因为 对一些被称为调用堆栈。 当你调用一个函数时, 系统留出内存空间 该函数来完成其工作。 我们呼吁内存这些块的 被预留给每个功能 调用堆栈帧或功能框架。 正如你所期望的, 这些堆栈帧 住在内存堆栈的一部分。 多个函数栈帧 可以在内存在给定时间存在。 如果主调用一个函数的举动, 与移动电话的方向, 所有这三个功能都开放框架。 但他们并不都具有积极的框架。 这些帧被布置成堆叠。 而从框架 最近被称为 功能总是在堆栈的顶部。 这始终是有效的框架。 这里只有真正过1 功能处于活动状态的时间。 这是一个在堆栈的顶部。 当一个函数调用另一个 功能,它的排序按暂停。 排序是待命,等待着。 而另一个堆栈帧被压 入堆栈在它的上面。 而这将成为活动框架。 和框架立即 下面需要等待 直到它再次活动框架 才可以恢复工作。 当一个功能是 完整,它的完成, 其框架被弹出堆栈。 这就是术语。 和框架立即 在它下面,正如我刚才所说, 成为新的活动框架。 而如果它调用另一个函数, 这将再次暂停。 这个新功能的堆栈帧会 被压入堆栈的顶部。 它会做的工作。 它可能弹回了。 和其它功能 下面就可以再次恢复。 因此,让我们通过这一次,看 在阶乘函数的想法 我们在定义 递归视频看 究竟这背后的魔力 递归过程正在发生。 所以,这是我们整个文件,对不对? 我们定义了两个 functions--主的事实。 正如我们所预期的, 任何C程序是怎么回事 处开始的主要的第一行。 因此,我们创造主一个新的堆栈帧。 而且它会开始运行。 主要调用printf。 和printf是要 打印出的5阶乘。 那么,它不知道 什么阶乘5, 因此这个调用已 根据另一个函数调用。 所以主要是要暂停在那里。 我要离开了 箭头在那里,颜色 它的颜色相同的 堆在右边框, 以指示主要是要冻结 在这里而5阶乘被调用。 所以阶乘5被调用。 而且它会启动在最 开始阶乘函数。 它问这个问题我会等于1? 是5等于1? 哦,不。 因此,它会下去 else部分,返回n倍 阶乘ñ减1。 嗯,好吧。 所以,现在的5阶乘是 根据另一个电话 到阶乘,传递 在4作为参数。 所以的阶乘 5架,即红色边框, 会冻结在那里 在该行我已经指示 和等待的4因子,完成 它所需要做的,这样则 可以再次成为活动框架。 因此,在阶乘4开始 的阶乘的开始。 为4等于1? 没有,所以它会做同样的事情。 这将下井else分支。 它会得到该行的代码。 好了,我要回四倍。 呵呵,3--阶乘所以阶乘 4取决于3整理因子。 所以它需要调用的3因子。 这就是要通过 再次同样的过程。 它开始通过,送过来。 3阶乘依赖 在1阶乘。 所以阶乘2开始,送过来。 这取决于1阶乘。 阶乘的1开始。 好。 所以,现在,我们正在 有趣的地方,对不对? 所以,现在,1等于1。 因此,我们返回1。 在这一点上,我们正在返回。 该函数的实现。 它的行为is--有 闲来无事为它做, 因此对于堆栈帧 1阶乘弹出关闭。 都结束了。 它返回1。 而现在,2阶乘,这 立即低于它的帧 在栈,成为活动框架。 它可以拿起 正是离开的地方。 它一直在等待一个阶乘 1完成其工作。 如今,它已完成。 所以,我们在这里。 1阶乘返回值1。 所以阶乘的2个CAN 说回2次1。 它的工作现在已经完成。 它返回2阶乘 3,这是等着呢。 的3因子是现在顶框, 活动帧在堆栈中。 所以它说,好了,好了,我要去 返回3次2,这是6。 而我要去给那个 值回阶乘 4,已在等着我。 我受够了。 3的阶乘离开本层,并 4阶乘是现在的活动框架。 4说,OK,我要回到4倍 3阶乘,这是六。 这是值 3阶乘返回。 所以,4次6是24。 而我要通过 这回阶乘 5,已经在等着我。 5阶乘现在是活动框架。 这将返回5倍 的4-- 5次24,或120--阶乘 并给予该值 回到主,它具有 一直在等待很耐心的 长时间在堆栈的底部。 这就是它开始。 这让这一呼吁。 几帧接手顶部。 现在是回到了堆栈的顶部。 这是活动框架。 因此,主要得到了价值120 回从5阶乘。 它一直在等待 打印出该值。 然后,它的完成。 有没有主多行代码。 因此,主要的弹出框关闭 堆栈,我们就大功告成了。 这就是递归如何工作的。 这是堆栈帧是如何工作的。 这些函数调用 以前发生 只是在暂停,等待 为随后的呼叫 完成,这样他们可以成为活动 框架和抛光他们需要做的。 我是道格·劳埃德。 这是CS50。