如果说学习过《计算导论与C语言基础》，你已经迈入了C语言的殿堂，那么《C程序设计进阶》将帮助你更上一层楼，理解“结构化程序设计的基本思想”，掌握“C程序设计的基本技巧”，养成“良好的编程习惯和编程风格”，编写出“真正具有生命力的计算机程序”。完成这门课的学习，你将能解释C程序设计语言的基本概念与知识，并且使用C语言编写计算机程序解决生活工作中的实际问题。
递归应用示例（进制转换、汉诺塔）
Loading...
From the course by Peking University
C程序设计进阶
606 ratings
From the lesson
函数的递归
本次课是C程序设计部分的一个难点。但，请不要担心，我们将按照“由简单到复杂”的方式进行讲解。我们先为大家讲解“递归调用”的执行过程，以便让大家看到“其实，递归调用与普通函数调用没什么不同”的道理，在此基础上，再去详细分解递归调用的过程，以印证我们学到的知识。
在此基础上，我们将通过几个典型的递归函数设计范例，向大家讲授递归函数的作用和使用技巧。
需要强调的是，如果在这个部分大家感觉到困难，请不要气馁：）因为，根据我们的教学经验，80%以上的同学都会感觉到同样的困难。当你也感觉困难时，可以先耐心听完我们的讲解，然后再通过练习慢慢体会。只要稍加练习，这个困难的感觉就会逐渐消失，因为，到那时，你已经对递归越来越熟悉了：）
Meet the Instructors
Ge Li 李戈, Ph.D.Associate Professor
School of Electronics Engineering and Computer Science
那下面呢,我们再来看一下递归程序的第二个应用场景。
我们可以用递归呀来模拟连续发生的动作。
好，首先呢我们也是先看一个例子。
那么看到这个例子，大家都非常的熟悉。啊这个例子呢是把一个十进制的数，
比方说123转换成了相应的二进制数1111011。
现在啊我们希望大家写一个递归的
程序。这个程序呢要接受一个十进制的数作为输入，
并且呢打印出它所对应的二进制数。 那怎么来写这个程序呢？我们来分析一下。
首先我们来看一下这个计算过程。要想求解123所对应的
二进制数，我们采取的办法是这样的。把123啊
除以2，我们会得到一个商和一个余数。
如果这个商啊不等于0，我们就
继续把这个商除以2，然后再得到一个新的商和
一个余数。然后如果它不等于0，我们再对它进行除以2，然后得到一个新的商和一个余数。
然后再判定一下它这个结果是不是0，如果不是0的话再除以2，然后又获得一个余数。然后再判定这个结果
是不是0，然后再除以2得余数。判断结果是否是0，除以2得余数，判断结果是否是0，除以2得余数。
你看在这个过程里头，是不是我们在反复的重复这个动作啊。
OK，好。那么既然我们一直在重复这样一个
过程，我们就可以用一个函数来描述这个过程。
比方说我们有这样一个函数叫convert，这个函数呢 能够描述刚才我们不断重复的那个动作。
啊也就是说，刚才我们其实一直在执行这样一个动作， 面对任何一个新的输入x，我们首先要判定一下
这个x除以2是否等于0。
如果它不等于0，我就把x除以2，然后呢重复下一个
动作。并且呢，我把x模2的值打印出来。
那如果x除以2等于0，那就意味着x不是0，就是1，
那这个时候很好办，我就把x打印出来，是这样的一个逻辑。
那说到这我们来看一下，是不是这个函数的函数体就描述了
刚才我们不断反复执行的那个动作呀。是不是啊？哎。
所以说对于这样的一个问题我们可以这样来思考。我们假设啊
有一个函数它能够完成我们反复执行的这个动作。
那么借由这个函数呢，我们再把这个动作的序列，这个动作执行的方式给它描述下来。
那于是呢我们就获得了一个递归函数。
那么有了这样一个递归函数体，我们再去写程序也就变得容易了。我们看一下这个程序。
这就是我们所定义的convert。 因为在convert的里面我们会处理所有的输出，所以说我们不需要
convert返回任何的值。所以说它的类型是void的类型。
那么在主函数里头呢，我们只要直接去调用一下convert，
就可以了。那么在这呢有一点我需要多说明一下。
在这儿啊，我们我们把每一个二进制位的输出
放在了递归调用之后。为什么要放在递归调用之后啊？
那是因为我们以前讲过，去计算一个十进制数的二进制的时候，最后的输出是一个
反向输出的过程。也就是说只有把cout
放在递归调用之后，它才会逆序打印出来。
这是刚才我们曾经讲过的一个特性。于是呢，我们来看一下这个程序的执行结果。
输入123，输出1111011。
这个结果是正确的。那么通过这个例子，我们可以看到，我们可以用递归的这种方式
来描述那些反复连续发生的动作。
OK。我们再来看一个例子。
这个例子啊非常非常的经典。
它就是汉诺塔问题。这个例子经典到什么程度呢？
那么基本上呢我们可以用这个例子来区分一个同学是否是学过计算机的。
啊那么基本上学过计算机的人都会知道汉诺塔问题。
OK我们来看一下什么是汉诺塔问题。
相传哪在一个古印度的庙里面，
这个庙宇的名字我也不知道该怎么去读啊。那么在这个庙里面呢，
有一个僧人，大概是在修行吧。他整天把三根柱子上的金盘啊
倒来倒去，他想把64个一个比一个小的金盘从一根柱子上
移到另外一根柱子上去，而且呢移动的过程要恪守以下的规则。
每次啊只移动一只盘子， 而且呢大盘子永远都不能放在小盘子的上面。
OK。我来解释一下这个事。我们来看这个图，在这个图上啊有三根柱子。
在第一根柱子上面放了一些圆盘。这个圆盘呢，大小是不同的。
大的圆盘在下面，小的圆盘在上面。那现在
这个僧人做的事情呢，就是把这一堆的圆盘
从这根柱子上移到这根柱子上。那就有的同学说，哎呀 这个移动还不很简单嘛，直接把这个圆盘拿起来放过来不就完了嘛。
不行。啊有这样一个规则，第一个，
每次移动这个盘子的时候啊只能移动一个盘子。
也就说你不能同时搬动两个或者两个以上的盘子，是不允许的。
这是第一个规则。第二个规则，你可以啊利用中间的这根柱子， 你可以用它来做缓冲啊。
但是每次出现在柱子上面的圆盘都必须满足一个条件。什么条件呢？
大的圆盘永远放在下面。小的圆盘永远放在上面。 也就是说，不能出现
大的圆盘在上面小的圆盘在下面的这种情况。OK，这就是
所有的这个规则。OK为了辅助大家来了解这个规则啊。我们来看一个动画。
好，我们来看这个动画。那么在这个动画上呢，有三个柱子，一、二、三，三个柱子。
其中呢，第一个柱子上放了好些圆盘。啊你看所有的盘子的罗列都是底下大，
上头小。然后呢我的任务是把这三个盘子从第一根柱子移到第三根柱子。
那么能不能一次把它三个盘子全搬起来啊？不行。我每次只能动一个盘子。
啊这是一个规则。那么要把最底下的这个盘子从
这个柱子移到这个柱子，那么我就必须要把上面的这两个盘子找个地方先放一下。
当然了，我可以用中间的这个柱子啊来做缓冲。这是允许的。
但是缓冲的过程中呢，又不能够把把这个盘子这样摞起来。因为如果这样放的话，
就会大盘子就会在上面，小盘子在底下。这又违这就会违反规则。所以这是不允许这么去放的。
所以说呢，为了能够把上面的这两个
盘子缓冲到中间的这个柱子上，我需要这么做。
啊先把这个移过来，再把这个移过来， 然后呢再把这个移过来。
OK，那么这两个盘子就被缓冲到中间的这个柱子上了。而且呢，大的盘子在下面，小的盘子在上面。
然后呢底下这个盘子你就可以从这移动到第三根柱子，把它放下来。
那现在呢，我们需要把这两个盘子移动到这来。毫无疑问，我们又要用
第一根柱子做一个缓冲，啊我们要把这个圆盘先暂时放在这。
然后呢把第二个圆盘把它放过来。然后第三，第一个盘子再给它放下来。 OK。那这样呢，我的这个移动就完成了。
那么通过这个过程啊，我们就会看到当盘子数目增加的时候，其实要移动这些盘子还是挺麻烦的。对不对？ 那么有人呢就简单地计算过，如果以每秒钟
移动一个盘子这样的速度来计算的话，
那么按照这个规则要移动具有64只
盘子的一个汉诺塔，那么就需要多长时间呢？ 需要5800亿年。
哇，这是一个太长太长的时间了。基本上这件事情是不可能完成了，对不对？啊，那么 既然人不能完成，那么现在呢我们就来写一个程序，来模拟一下盘子的移动过程。
什么意思呢，就是要写一个程序把盘子搬动的过程啊给它打印出来。
那么为了让大家明白我们需要写一个什么样的程序。我们先来看一下这个程序的运行过程。
比方说对于刚才的汉诺塔的问题。我们假设啊三根柱子的名字分别
叫做A、B、C。我就可以这样来打印。程序运行起来之后呢，首先提示
请输入盘子的数目。假设说我输入的是4个。那么程序呢就会打印出来
在三根柱子上移动四只盘子的步骤为。
底下每一行就是一个步骤。比方说第一行。
把一个盘子从a移动到b，这是第1步。
第2步呢，把一个盘子从a再移动到c，
那么第3行呢，把一个盘子再从b再移动到c，
然后第4行呢，把一个盘子从a再移动到b，等等等等。每行一个步骤，那么现在需要我们做的，
就是要写一个程序，当用户给出来一个n，我们就把这个步骤，
给它打印出来，这是我们要完成的事情。那现在的问题来了，
怎么去解决呢？那么看上去这个问题还是
有点难，当碰到这样问题的时候啊，
我就想起来，我们刚刚开始c程序设计这个部分的时候，曾经给大家讲过的，
当你面临一个问题的时候啊， 你一定要先去思考这个问题的
解决方案，因为没有解决方案就没有程序。
所以阿，我们先放下程序不说，我们先来考虑
一下解决这个问题的方案。我们先来分析一下这个问题。
还是那句话，既然要分析问题啊，我们就要从最简单的情况开始考虑。
假设说现在只有一个盘子需要我们移动，
那么对于一个盘子的情况实在是太简单了，对不对？我们只要把这一个盘子从
a上面拿起来放到c上面，就ok了，这是一个盘子的情况。
那两个盘子的情况呢，也很简单。比方说， 我要把这两个盘子从a经过b移动到c，
那么应该怎么办啊？很简单，我们可以把a上面的这个小盘子先拿起来，
放到b的上面，然后呢再把底下这个大的盘子移到
c的上面，然后呢再把b上面的这个小盘子，移到c的上面，
这是两个盘子的情况。那么三个盘子的情况呢？
为了把a柱子上面三个盘子通过b柱子移动到c，
我们只能这么做。怎么做呢？把a柱子上面，
上面的两个盘子先移动到b柱子上，
然后a柱子上这个最大的盘子就可以移动了，于是呢我们就把a柱子上的这个
最大的盘子从柱子移动到c柱子，在c柱子上放好以后，
我们再把b柱子上的这两个盘子移动到c柱子上面去，那么这三个盘子就都
被移动到c柱子上了。那有的同学说，那怎么才能把
a柱子上最上面的两个盘子移动到b柱子上呢？
有怎么样才能把b柱子上面的两个盘子一下子移动到c柱子上呢？
我说啊，这个过程一点都不复杂。因为刚刚你已经解决过了。
你看我们在第2步，是不是已经移动过两个盘子啦。
是不是？我们在第2步已经把两个盘子
从a柱子跨越b柱子移动到c柱子上面了。
那么在这，当我们想把两个盘子从a柱子 上面移动到b柱子上面的时候，那我们只需要把
这儿的c柱子当作刚才的b柱子来使就可以了。
所以说阿，当我们要移动三个盘子的时候，我们完全可以把它
化简成以两个盘子的情况，也就是说啊，我们可以
得出来这样一个表示，我们要实现把三个盘子从
a柱子上面通过b柱子移动到c柱子， 那我应该怎么办呢？我完全可以这样来做。
先把a柱子上面的两个盘子 从a柱子上面经过c柱子移动到b柱子上面，
这就是我们刚才所叙述的这第一个过程。然后呢，
我把第三个盘子从a柱子上再移动到c柱子上，
这就对应着我们刚才所进行的第2步。
进行完这两步之后呢，然后再把两个盘子从
b柱子上经过a柱子移动到c柱子上，这就对应着
刚才的第3步。那么通过这样3步，
是不是我就可以把三个盘子从a移动到c啦。
ok，是这样的。通过这个分析我们就可以看到，是不是移动三个盘子的问题
就被简化成了两次移动两个盘子的问题啦。
对于对？那么我再问一下，如果对于四个盘子的情况呢？
那如何移动四个盘子的情况就会被简化成如何移动三个盘子
的情况。然后呢，进而又被简化成你如何移动两个盘子的情况。
这样一步一步下去，当我们有n个盘子的时候，
就被演化成了如何移动n减1个盘子的
情况了。好，那么接下来就来看一下如何移动n个盘子。
这有n个盘子，我们不去管它一共有几个阿。我们假设这一共有n个盘子，
那当我想把这n个盘子从a柱子上面经过
b柱子移动到c柱子上面的时候，
我是怎么来进行的呢？ 一样的办法。既然要从a柱子上移动到c柱子上，
于是呢，我就必须要把a柱子上面
除了最底下这个盘子之外的所有其他
盘子先从a柱子移动到b柱子， 先给它从a移动到b。
移动完毕以后呢，第2步，再把a柱子上
最底下的这个盘子给它移动到c柱子，移动到c。
那么这个完成了以后呢，再把b柱子上所有的盘子从b柱子再移动到
c柱子。那完成这个步骤以后呢，那么所有的盘子就都在
c柱子上了。如果我们把刚才的这个整个的这个过程
写下来的话，那么可以表述成这个样子。
如果我们想要实现把n个盘子
从a柱子上经过b柱子移动到c柱子， 那么我们应该这样去做。
先把a柱子上面最上面的n减1个盘子，
从a柱子经过c柱子移动到b柱子，
然后呢，再把a柱子上面剩下的这个盘子，移动到c柱子。
那么移动完以后呢，再把刚刚移到b柱子上的n减1个盘子，
从b柱子经过a柱子移动到c柱子。
那么这样一个描述也就告诉我们，对于想要移动
n个盘子的情况，我们完全可以把它化简成要移动 n减1个盘子的情况。
也就是说阿，当我们有5个盘子的时候，我们就可以
约简成4个盘子的情况，有4个盘子的时候我们就可以约简成有3个盘子的情况。
有3个盘子就可以约简成有两个盘子的情况，那有两个盘子的情况我们就
可解了。那步骤是我们已经知道的。于是整个这个问题就可以解决了。
是不是这样的呀？所以如果把这个
逻辑描述下来呢，我们就可以得到一个这样的程序。
我们来看一下这个程序。 假设阿，有这样一个函数move,它呢表示要把m个盘子从
原始的柱子，这个x呢表示起始的柱子，经过
中间的柱子y移动到最终的柱子z.
有的同学说，哎，你在这为什么不使用abc呢？
因为在移动的过程中啊，哪个柱子是原始的柱子
哪个柱子是最终的柱子，哪个柱子当中间的柱子使用
是一件不断变化的事情。所以说呢，我在这用了3个变量，
把它们当作变量写在函数参数里头。 那么当我们想把m个盘子
从x柱子经过y柱子移动到z柱子的时候，
我们就需要这么去做。先判定一下m是多少.
如果m等于1，也就是说只有一个盘子，那我们就直接把这个盘子从x移动到z,
从原始移动到目标。 如果m不等于1，那我们就把最上面的m减1个盘子
先从原始的起点，经过z，移动到y，
然后呢，我们再把x上面剩下的最后一个盘子从x移动到z,
之后呢，我们再把刚刚移动到y上面去的m减1个盘子从y上面，
经过x，移动到z。就是这样的一个逻辑。
那么有了这样一个逻辑之后，我们再去写程序就变得容易了。我们来看一下这个这个程序。
这个呢，是刚刚我们所定义的move函数，它表示啊，
把m个盘子从与原始的数字x
经过中间的柱子y移动到目标柱子z上面去，
这是它的含义。那么在主函数里头呢，我们输入一个盘子的数目，
然后呢，直接去调用move这个函数，
并且呢，我们去写明每一个柱子的名字。
比方说，我们是把原始的柱子命名为a，把中间的柱子命名为b，
然后呢，把目标柱子命名为c。那么这个调用呢，就表示我要把
n个盘子从a经过b，移动到c，
那么结果会是怎样呢？我们来看一下运行的结果。输入4，
然后呢，它就会打印出来每一步运行的步骤。ok,我们来总结一下。
通过这两个例子，我们可以看到 我们可以利用递归啊，来模拟连续发生的动作。
我们可以通过这种方式阿，来解决问题。那么，当我们想通过这种方式
解决问题的时候我们应该怎么去思考呢？也就说那个方法是什么呢？我们首先来看，
第一，首先你要搞清楚，那么连续发生的动作
它是什么。比方说在第一个例子里头，那个连续发生的动作就是
你需要不断地对十进制数处以2，得到
余数，并且判定商是否等于0。
那么在刚刚我们所讲过的汉诺塔问题中呢，你需要不断的做的动作就是
把m个盘子从原始的柱子x
经过中间的柱子y移动到柱子z，你首先要搞清楚，那些连续发生的动作
是什么。其次呢，在这个基础上，你要搞清楚不同次动作之间的
关系。这个关系是什么？比方说，在进制转换的例子里头，那个关系
就是把商当作下一次你要除的那个
十进制数。 在刚刚我们讲过的汉诺塔的例子里面，那么
不同次动作之间的关系其实就意味着
当我要移动m个盘子的时候，我需要先把m减1个盘子
移动出来，然后呢，再把底下的[盘子从x移动到z,
然后再把刚刚移出来的m减1个盘子从y移动到z。
这就是前一次动作和后一次动作之间的关系是什么。
然后在这个基础上，你还需要确定一点，那就是要确定
边界条件是什么。比方说，再刚才我们的汉诺塔的例子里头，
边界条件就是当m等于1，也就是说只有一个盘子需要移动的时候那就好办了。盘子直接
从x移动到z就可以了。那么搞清楚这3点之后，
我们就可以根据第一点来定义那个函数。
根据第2点来描述递归函数之间的关系，
然后第3点呢，来描述递归推出的边界条件。
于是整个程序你就可以得到了。这就是当我们利用
递归来模拟连续发生的动作这样的一种方式 来解题的时候，我们需要做的一些事情。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
