C#（又称csharp)是一种优秀的面向对象语言，它继承了C++和Java等语言的优点，在Windows图形用户界面、Web应用、数据库等方面有着广泛的应用。本课程在介绍C#语言及面向对象的程序设计基本原理的基础上，使用Visual Studio作为开发工具，介绍C#对各种常见的信息的处理方法，包括文本处理、图形绘制、图像处理、多媒体、网络信息获取、数据库应用等。 课程中除了理论知识外，更注重上机编程实践，程序示例紧密结合日常的学习和工作，生动有趣，难度适中。 本课程要求学习者学过一门程序语言（如C语言等）。
递归算法
Loading...
来自 北京大学 的课程
C#程序设计
38 评分
从本节课中
第5讲 基础类及常用算法
从本讲开始，要介绍的是C#语言类库及其应用。本讲首先介绍基础类和工具类，包括数学类、日期类、字符串等；然后讨论一些常用的数据结构，包括集合、堆栈和队列以及在它们上面实现排序及查找；最后，本章还将介绍一些常用算法，如遍试、迭代、递归等。
与讲师见面
唐大仕博士
北京大学信息科学技术学院
下面呢我们一起来学习递归
递归呢，从逻辑上来说呢就把一个问题呢划归为同样 的简单一点的问题。
所以在形式上呢就是自己调用自己 我们下面先看一个简单的例子，就是求阶乘
先看呢这个阶乘呢 阶乘呢就表示从
1 乘 2，乘 3，乘 4，一直乘到 n 表示 n 的阶乘，比如说
6 的阶乘 然后 6 的阶乘呢就是 6 乘 5 乘 4 乘 3 乘 2 乘 1，等等 一直乘到 1。
那注意到这个 5 乘 4 乘 3 乘 2 乘 1 实际上它是 5
的阶乘，所以呢我们在求 6 的阶乘的时候 可以说呢 6 的阶乘等于 6
乘以 5 的阶乘 那么更一般的就是说 n 的阶乘怎么求呢？那就是
n 乘以 n-1 的阶乘，所以写成程序呢就是 fac，然后呢就等于
fac(n-1) 乘以 n，就是 n 的阶乘 就等于 n-1
的阶乘乘以 n，这是我们发现 它是阶乘的问题里面呢，又用了阶乘
所以就把它自己的问题呢划归为自己的问题，同样的问题，但是呢
一般说规模稍微小一点呢 n-1 了，另外这是一个要素。
另外还有一个呢，一般说呢 我们到 n 等于 1 的时候，它 return
1，所以 这也就是说 1 的阶乘就是 1，那 0 的阶乘那就什么也不乘，那也就是
1 了 所以它的阶乘的两个要素，一个要素呢就是有一个递归出口，就是一种特殊情况
第二个呢，一般的情况呢，它就是我们要自己又调用自己
所以阶乘这个问题呢，我们这里就是用递归的方法来书写的 刚才这个阶乘问题里头，它之所以能够
计算机能够执行呢，这实际上是因为我们告诉它的是 任何一个 n 的阶乘。
所以呢虽然我们说 6 的阶乘 然后让它要算 5 的阶乘，但实际上我们把
5 的阶乘已经告诉它了 因为 5 的阶乘呢，它就是 4 的阶乘乘以 n 但实际上 4 的阶乘我们也告诉它了。
所以它就这样一个递归的一种调用 下面我们看看一个走台阶的问题。
我们平时呢这个台阶呢我们 上台阶的时候可以，有时候是一步呢走一个台阶，有的时候一步可以走两级台阶
我们这里是台阶 我们看
0 级台阶 那当然是一种走法，0 级台阶我们可以不管它了，1
级台阶有几种走法呢？ 1 级台阶是一种走法，这个就一步，这里呢就一步 就跳上去了。
然后呢，2 级台阶呢？ 1 步跳两级台阶，或者是呢一步，再走一步，所以
2 级台阶呢我们就有两种走法 那 3 级台阶呢，那就是一步一步再一步，或者是一步两步
或者是两步一步，所以 3 级台阶呢有三种走法 那么
4 级台阶有几种走法呢？是不是四种走法呢？
我们可以试验下，就是一步一步一步，一种走法
一步两步一步，这个或者两步一步，所以 4
级台阶这个走法，我们看这个用这样列举的办法那就很难列出来了 那如果是
9 级台阶我们要这样列举那就更困难了，所以我们得换一个思路
这个换个思路呢，怎么考虑这个问题呢？就是我们看 9
级台阶 9 级台阶呢，第一步，我们考虑 9 级台阶走第一步，第一步呢
它是要么走一个台阶，要么呢走两个台阶，所以我们发现呢，那剩下的问题是什么呢？ 如果走一步的话，所以
9 级台阶呢，走一步呢，它这个走法呢，实际上有两种走法的合成
一种呢是走一步还剩 8 级台阶，如果是走两步呢，还剩
7 级台阶 所以这样一个方法呢，它就是 9
级台阶呢就等于 8 级 台阶加上 7 级台阶的走法的总和。
所以更一般的呢就是 n 级台阶呢是 n-1 级台阶和 n-2
级台阶的走法的总和 当然我们有个特殊情况，就是 1 级台阶的时候或者 0 级台阶呢
它的总和只有一种，我们把它写成程序呢就是一个递归的 因为它是自己
9 级台阶又化成了台阶问题 那程序写起来呢，反而简单了
n 级台阶的走法，我们假设叫 fib(n)，然后呢如果是
0 和 1，这个要素呢 它就只有一种走法了，那么
else，就是一般的情况下，第二个要素呢就是 n-1 级台阶加 n-2 级台阶的走法的和。
当然由于我们告诉这个 n 是任意的，所以它就会 进一步地往下去走，所以这就是 n 级台阶。
如果我们要算 10 级台阶呢，就 fib(10) 就可以调用
所以它的基本形式呢就是自己调用自己，另外呢有一个特殊情况，我们也把它称为呢 递归出口。
而递归程序写起来呢都是相当简洁的，简洁的要命
实际上呢这个有一个术语呢叫斐波那契数列，就是后一项等于前两项之和
这个是斐波那契这个数学家提的这么一个数列。
一般的描述呢就是说 是兔子的问题，我这里描述成台阶问题，那兔子呢它是这样说的
如果有一对兔子，第一个月呢是小兔子，然后第二个月 长成中兔子，第三个月呢就是老兔子，但是这个老兔子第三个月的时候呢
它会再生一对兔子，以后每个月老兔子都会生一对兔子 那么原先中兔子呢又会长成老兔子，老兔子又会生
那问你呢，原先一对兔子呢十二个月以后有多少对兔子
这也是一个就是斐波那契数列，当然这个数列呢还有点点绕
如果不用递归呢还有点绕，我经常在想呢，要是我是那一对兔子
我真的不知道十二个月以后是多少，所以人是最聪明的
