数据结构与算法5: 递归(Recursion)
数据结构与算法5: 递归(Recursion)
《软件随想录：程序员部落酋长Joel谈软件》一书中《学校只教java的危险性》一章提到，大学计算机系专业课有两个传统的知识点，但许多人从来都没搞懂过，那就是指针和递归。我也很遗憾没能早点熟练掌握这两个知识点。本节一些关键知识点和部分例子，都整理自教材或者网络，参考资料列在末尾。如果错误请纠正我。
1)什么程序具有递归解决的潜质?
2)递归还是非递归算法，怎么选择?
3)递归程序构造的一般模式
1.递归定义
首要引入递归定义这一概念。
通常我们定义一个新概念，总是使用已经定义过的或者意义显然的术语，而递归定义则是一种根据自身概念定义自身的定义。
例如阶乘函数的定义：
例如斐波那契数列定义如下:
递归定义，主要有两个作用，一是产生新的元素，另一个是判断一个元素是否属于某个集合.
具有这种递归定义的函数，是很容易编程实现的。
2. 递归是怎么实现计算过程的？
假设我们讲上述阶乘函数转换为程序代码如下:
//using recursion
int factr(int n)
if ( n ==0) return 1;
return n*factr(n-1);
我们调用fact(3)则返回6，这里有一个疑问，我好像什么都没做啊？
如果我们选用他的迭代实现：
//using iteration
int facti(int n)
int result = 1;
for(int i = 1 ; i <=i++)
则感觉是在利用累乘计算我们的阶乘，一下子就比较清楚了。我们的疑问在于： 递归实现中，是怎么执行计算过程的？
首先要了解中函数调用时大致情况(此处不详细学习，要想更深入和全面，请参考:Wiki Call stack)。在高级语言编写的程序中，调用函数和被调用函数之间的链接及信息交换通过栈来进行。（该段参考自【1】）
通常，在运行被调用函数之前，系统需要做3件事，包括:
将所有的实在参数、返回地址等信息传递给被调用函数保存 为被调用函数的局部变量分配存储区 将控制转移到被调用函数的入口
从被调用函数返回调用函数之前，系统也要完成3件事：
保存被调用函数的计算结果
释放被调用函数的数据区 依照被调函数保存的返回地址将控制转移到调用函数
归纳起来，就是函数调用的过程中处理要素包括：函数控制权的转接工作（利用函数入口地址和返回地址），局部变量的空间分配工作，实参和形参的传递，函数的返回结果传递。一个函数的状态由一个5元组决定,即function(入口地址，返回地址，形参值，局部变量值，返回值)。保存所有这些信息的数据区称为活动记录（activation
record）或者叫做栈结构(stack frame),它是在运行时栈上分配空间的。活动记录，在函数开始执行的时候得到动态分配的空间，在函数退出的时候就释放其空间。main函数的活动记录比其他活动记录生命周期长。
这里注意的是，活动记录保存函数参数的时候，既可以值传递也可以传递地址，如果是值传递则保存数据元素的副本，如果是传递数组或者按引用则活动记录包含数组第一个元素的地址（数组首地址）或者该变量的地址。同时对于局部变量，活动记录只包含他们的描述符和指向存储它们的位置的指针。
简单的函数调用过程,例如如下代码:
int main()
/*110*/ first(m,n);
/*111*/ ...
int first(int s,int t)
/*210*/ second(i);
/*211*/ ...
int second(int d)
那么函数调用的过程中形成的活动记录栈的内容如下:
对于递归函数调用，表面上看，好像我们什么都没做，就完成了功能，实际上在函数递归调用的过程中，函数的活动记录不停的分配和回收，计算过程在进行着。
递归调用不是表面上的函数自身调用，而是一个函数的实例调用同一个函数的另一个实例。(参考自【2】)
我们将上面的阶乘函数重写，标上一个地址标号(这是一个粗略的标号，实际上底层的机器地址不是这样的):
int main()
/*102*/ int n = factr(3);
/*103*/ std::cout << "Factorial of "<<n<<" : "<<factr(n)<<std::
//using recursion
/*201*/ int factr(int n)
if ( n == 0)
return n*factr(n-1);
则我们在main函数中调用fact(3)是执行的活动记录过程如下:
可以看出实际上递归调用时，系统不停的分配活动记录，调用从main()--->fact(3)--->fact(2)-->fact(1)--->fact(0) 一层层深入，然后再一层层回退，直到main函数中。由于活动记录中保存了函数局部变量，因此每次调用之间互补干扰，从一个被调用函数返回调用函数时能够保证计算出准确的结果，并返回上一层的函数，依此进行。活动记录栈是分析递归程序的一种好的方法。
3.递归类别
递归有许多级别和许多不同量级的复杂度。
我们从尾部递归与非尾部递归，直接递归和间接递归来分类了解。
简单的如，尾部递归。尾部递归，即那种在函数实现的末尾只使用一个递归调用。尾部递归的特点是，当进行调用时，函数中没有其他剩余的语句要执行，并且在这之前也没有其他直接或者间接的递归调用。
尾部递归示例程序:
void printListi(list::iterator itCur,list::iterator end);
void printListr(list::iterator itCur,list::iterator end);
int main(int argc,char** argv)
for(int i = 0;i < 10 ;i++)
iList.push_back(i);
if ( argc == 2 && string(argv[1]) == "-r")
printListr(iList.begin(),iList.end());
printListi(iList.begin(),iList.end());
//using tail recursion
void printListr(list::iterator itCur,list::iterator end)
if( itCur == end)
std::cout<<std::
std::cout<<*itCur++<<" ";
printListr(itCur,end);//at tail ,call itself
//using iteration
void printListi(list::iterator itCur,list::iterator end)
while(itCur != end)
std::cout<<*itCur++<<" ";
std::cout<<std::
这里使用尾递归或者迭代方式输出链表内容，可以看出尾递归只是一个变形的循环，可以很容易用循环来代替。在含有循环结构的语言中，不推荐使用尾部递归。
除了尾部递归，当然存在非尾部递归，例如:
void reverse1();
void reverse2();
void reverse3();
int main(int argc,char** argv)
std::cout<< "input somethind:"<<std::
reverse2();
std::cout<<std::
//all chars reverse,no newline
void reverse1()
std::cin.get(ch);
if( ch != '\n')
reverse1();
std::cout.put(ch);
//with newline at head line,other chars reverse
void reverse2()
std::cin.get(ch);
if( ch != '\n')
reverse2();
std::cout.put(ch);
//output only newlines
void reverse3()
//note the static
std::cin.get(ch);
if( ch != '\n')
reverse3();
std::cout.put(ch);
这里提供了三个版本的函数，旨在帮助理解递归调用特性。版本1，会对输入进行逆向输出，另外两个版本你可以分析其输出。当然，可以利用栈或者缓存实现逆向输出的迭代版本。
上面的尾部和非尾部递归，都是直接递归，也就是函数自身调用自己。另外一种情形是，一个函数通过其他函数间接调用自身，例如f()-->g()-->f()这种间接形式。
还有所谓的嵌套递归，即函数不仅根据自身定义，而且还作为该函数的一个参数进行传递。例如Ackermann函数：
这种情形是很复杂的。vcD4KPHA+PGJyPgo8L3A+CjxoMj40ILXduem+rbXkzsrM4jwvaDI+CjxoMz40LjEgVG93ZXIgb2YgSGFub2k8L2gzPgo8cD66usW1y/7Oyszi0tG+rb2rtcS63LbgwcujrNXiwO+4+LP2xuS13bnpus21/LT6yrXP1qOsyLu688zWwtvSu9Cp16LS4rXjoaM8L3A+CjxwPrX8tPqw5rG+tcTKtc/Wo6yyzr+8wctodHRwOi8vd3d3LmVjc2UucnBpLmVkdbXE18rBz6OsyLu689fU0NDV+8DttcSho7X8tPqw5rG+tcTKtc/Wt73Kvcjnz8I6PC9wPgo8cD69q8XM19O007Tztb3QobHgusUxLW4svavW+dfTseC6xTAsMSwyoaO55raoOjwvcD4KPHA+MSnDv7TO1rvE3NLGtq/Su7j2xcyjrMfS1rvE3L2r0KHFzLfF1Nq088XMyc/D5qGjPC9wPgo8cD4yKcXM19PFvMr9usXC68qxo6zR2NfFxObKsdXrt73P8tLGtq+8tDAtMi0xLTA7xczX08bmyv26xcLryrGjrNHY18XLs8qx1evSxravo6y8tDAtMS0yLTCjuzwvcD4KPHA+MynDv7TO0sa2r7XExczX07K7xNzKx8nPtM7Sxravuf21xMXM19M8L3A+CjxwPtei0uKjrMO/tM7SxravtcS5/bPM1tCjrNKq0aHU8dK7uPbJz7TOw7vT0NLGtq+5/bXExcyjrMTHw7TKo8/CtcTBvbj2xczX09bQo6y/z7ao09DSu7j2tPO6zdK7uPbQodCptcSjrNK7sOPX3MrH0aHU8dfu0KG1xNK7uPajrMjnufvDu9PQ1+7QobXE0ru49tTy0sa2r8THuPa087XExcwowP3I58HtzeLSu7j2w7vT0NLGtq+1xMXM0tG+rdG51NrBy7jVuNXSxravuf21xMXM19PPwsPmKaGjzazKscjnufuz9cq8yrHSxravxczX08r9xL/Oqsbmyv2jrNTy1+7W1cXM19PU2jG6xdb519OjrLfx1PLU2jK6xdb519OhozwvcD4KPHA+PGJyPgo8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:">// using recursion
void hanoiRecursion(int n,char src,char mid,char target)
if(n == 0)
// do nothing
hanoiRecursion(n-1,src,target,mid); // move the up n-1 stack to mid
cout<<"("<<n<<","<<src<"<<target<<")"<<// move the n-th stack to target
hanoiRecursion(n-1,mid,src,target);// move the up n-1 stack from mid to target
// using iteration
// if n odd then final post is 1,else is 2
void hanoiIteration(int n)
stack dStack[3];
dStack[0].push(i);
int lastItem = -1; //record last moved disk
while(!dStack[0].empty() || !dStack[n%2+1].empty())
//pick the smallest and not the last moved disk to move
int stackNum = 0,moveItem = n+1;
for(int i = 0;i < 3;i++)
if(dStack[i].empty() || dStack[i].top() == lastItem)
if(dStack[i].top() < moveItem)
stackNum =
moveItem = dStack[i].top();
lastItem = moveI
//move odd-numbered disk clockwise ,move even-numbered disk counter-clockwise
int target = (moveItem % 2 == 0 )?(stackNum+2)%3:(stackNum+1)%3;
cout<<"("<<moveItem<<","<<stackNum<"<<target<<")"<<
dStack[target].push(moveItem);
dStack[stackNum].pop();
两种实现方法移动的都是最少次数。
如何计算盘子移动次数？
一个性质是，只要盘子总数确定，不过从哪儿移动到哪个目的柱子，总共要移动的次数是一样的。
假设n个盘子移动次数为h(n),则我们可以计算如下:
可以看出当n=64时，数目极其巨大，无法在有效时间内解决。
Hanoi塔的迭代版本可以使用位操作实现，不过好像技巧性比较强，有兴趣可以参考:How
does this work? Weird Towers of Hanoi Solution.
4.2 Koch Snow
Koch雪花问题，设计到递归实现问题。关于其一般介绍可参考Wiki koch snow,这里主要讲述与递归实现相关的部分。
首先给出一个OpenGL绘制的效果图如下:
关于这个雪花的实现有3个重要的数学问题。
1)绘制的规律--利用转动角度和圆的坐标计算
首先发现一下规律。
上面分别为进行了0次分形，1,2,3次分形的图形，不管怎么分形有一个重要的性质(一开始我是没想到的，后来观察教材的实现代码是明白了)。
第一次从O1点计算出O2点，O2在其圆周上，利用圆心坐标公式:
prevX = prevX + (side/3)*cos(angle*PI / 180.0);
prevY = prevY + (side/3)*sin(angle*PI / 180.0);
即可计算，然后从O2点计算出O3点，这次在O2圆周上且圆周夹角为+60，后面angle依次加上-120度，+60，这样第一条便就绘制结束。第二条边与第一条边之间angle加上-120度，第三条和第二条也是angle加上-120度。这个angle是全局的，这一点性质很重要。
2)周长是无限的
每进行一次细分，则边的数目是原来的4倍，同时边的长度是上次的1/3，因此有:
当n趋于无穷大时，长度不收敛，为无穷大。
3)面积是有限的
面积推导也比较简单，每次分形后，面积都在前面的基础上增加，而增加的部分就是向外扩展的小三角形的面积。设原始边长为a,则前几次分形的面积计算如下:
通过发现规律，可以计算出n趋于无穷时的面积为:
由此可以看出，Koch雪花在有限的面积内，周长却无限大。
实际在利用OpenGL绘制Koch雪花时，只需要保存所有的点即可，然后一次渲染即可。
关键部分实现如下:
//predefined variables
std::vector vertexV//hold points
float prevX = 0.0f,prevY =0.0f;//the previous point
int angle = 0;
float side = 3.0f;
int level = 6;
//prepare snow data
void prepareData()
float originX = 0,originY =0;
vertexVec.push_back(glm::vec4(originX,originY,0,1));
for(int i=0;i< 3;i++)
drawFourLine(side,level);
angle += -120;
//draw four lines
void drawFourLine(float side,int level)
if (level == 0)
prevX = prevX + (side/3)*cos(angle*PI / 180.0);
prevY = prevY + (side/3)*sin(angle*PI / 180.0);
vertexVec.push_back(glm::vec4(prevX,prevY,0,1));
drawFourLine(side/3,level-1);
angle += 60;
drawFourLine(side/3,level-1);
angle += -120;
drawFourLine(side/3,level-1);
angle += 60;
drawFourLine(side/3,level-1);
代码表明，我们实际上把一个雪花看做3个4段组成的，而一个4段的每一段又可以继续分为4段，特殊情况例如没有分形时只有一条边，而这条边可以看做一个4段的特殊情况。
4.2 全排列问题
曾经遇到过一个全排列的问题，即给定无重复值的字符串，给出其全排列，例如ab,全排列即为ab,ba.
实际上在用递归实现时，基本算法描述为:
permutaion(input,output)
如果只有一个字符，则将字符添加到output即可;
每次从input中取出一个不同的字符作为头部字符head
然后拿出剩下的部分leftPart进行排列(返回的是一个子串的排列的集合)
对剩余部分排列的每个结果的首部加上头部head,得到的结果添加到output简单来讲，就是固定一个头部，然后让剩下的子串全排列，将头部和子串全排列的每个结果串链接起来，从而得到完整的全排列。
对于子串重复执行这个过程，直到遇到只有一个字符时，它不用排列了，直接返回即可。
算法实现为:
// permutation the input string and save it to result
void permutation(string input,vector &result)
if(input.length() == 1)
result.push_back(input);
for(string::size_type i= 0;i < input.length();++i)
string leftPart =
leftPart.erase(i,1);//get left part
vector strV
permutation(leftPart,strVec);// use
left part to permutate
// add this char with left part result
for(vector::iterator it = strVec.begin();it != strVec.end();++it)
result.push_back(input[i] + *it);
例如输入"abc",则输出结果为:
Permutation of: abc ,kind: 6
用递归实现的还有很多程序，例如迷宫问题，8皇后问题等等，不再列举。
5. 递归与非递归选择
刚刚学习python的时候写过一个Fibonacci数列的程序，如下:
def fibr(n):
"""get the n-th Fibonacci series number,using recursion"""
global callCnt
callCnt += 1 # count how many time function called
return fibr(n-1)+fibr(n-2)
当然这个callCnt是之后加上去的。程序运行正常，可是我输入n=40,n=100的时候，程序好像死机了，然后我就开始责怪python效率低(刚开始我没有分析复杂度，确实错怪了：)。
我们看下实际情形(粗略的时间估计):
~ python3 fibr.py 30
fib(30)=832040
called 'recursive function fibr' 2692537 times
consumed 371338 ms
**************************************************
~ python3 fibr.py 40
called 'recursive function fibr'
ms现在知道实际上在递归调用斐波那契数列时例如n=40时函数fibr调用了3亿多次，花了2分多钟才计算完毕!
同样书写了一份迭代版本，去除程序中多余的时间统计和函数调用统计语句后，粗略地比较了c++/Python计算的时间:
通过分析上述数据，可以得出:迭代算法的效率要比递归效率高，C++编译型语言执行计算时比解释型语言Python要快10倍左右(这个比较不代表python在其他方面没有优势)。
下面要对Fabonacci数列的递归实现和迭代实现做简单分析。
对于递归实现，归纳总结得出:
也就是说，对于Fib(n)，计算时执行函数调用2Fib(n+1)-1次，执行加法Fib(n+1)-1次。
而对于迭代实现:
//using iteration
long long fibi(int n)
long long tmp =
对于n>1,进入for循环，一共执行(n-1)次。每次循环中执行3次复制操作，隐含一个加法操作，那么一共需要3(n-1)次赋值和(n-1)次加法运算。
Fibonacci数列增长很快，迭代算法不需要递归调用的函数开销，同时加法和赋值操作也比递归版本少，因此，对于Fibonacci数列使用递归算法是不恰当的，应该采取其迭代版本。
这个例子告诉我们，虽然递归算法很容易书写，但是具体应该用递归还是迭代实现，应该视情况而定;最好对迭代和递归版本实现的复杂度和开销进行分析，或者在实际机器上比较算法执行效率。
对于递归算法，总结如下:
1)一般对如要解决的问题，如果能进行分解，且分解为一个和原问题具有相同特征，则可以利用递归实现。
例如移动Hanoi塔分解后就是将上面的(n-1)个塔从一个塔移动到另外一个塔；例如全排列问题，取出一个作为头部后，对于剩下的元素，同样要求出其全排列；对于迷宫问题，总是从当前位置开始，如果是结束位置则停止，否则尝试4个方向走出迷宫，每走到一个新位置，又作出同样的抉择。
2)递归程序的编写，有一个普遍的模式，即程序有一个基底或者叫做出口，另外的部分就是调用自身即可。请注意递归程序一定要选择好出口，否则就成了盗梦空间里回不来了。
出口部分，例如只有一个盘子的Hanoi塔，只需移动他即可；只有一个字符的全排列问题，只需要返回它即可;这些都是程序的出口。递归程序的一个模式就是:
function(param)
处理并返回;
function(param)
3)是谁在背后支持我们的递归调用？ 一个是语言本身的支持，另一个是操作系统的运行时栈的支持以及可能的硬件支持。
递归函数避免不了递归调用时的栈开销，但这也并不意味着它的效率一定比迭代方法低。
对如一个问题，迭代实现和递归实现需要作出比较和分析，然后确定到底使用哪种算法实现。
如果想进一步了解，可以参考[4]上面的讨论。
最后，贴上StackOverflow上面的关于递归的一个挺有趣的解释:
A child couldn't sleep, so her mother told her a story about a little frog,
who couldn't sleep, so the frog's mother told her a story about a little bear,
who couldn't sleep, so the bear's mother told her a story about a little weasel...
who fell asleep.
...and the lit
...and the lit
...and the child fell asleep.
《数据结构》
严蔚敏 吴伟明
清华大学出版社
[2] 《数据结构与算法 c++版 第三版》
Adam Drozdek编著
清华大学出版社
Wiki Tower of Hanoi
What is recursion and when should I use it?
Koch snowflake
[6] a simpler iterative solution
to the towers of hanoi problem数据结构--算法（21）
递归算法:是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
递归的应用：
1.变位数(全排列单词)
思想：假设对n个字母的单词全排列
1、全排列最右边n-1个单词
2、轮换所有的n个字母(即单词左移一位，保证每个字母有机会排在开头)
3、重复以上步骤n次
public class ArrangementWord {
priv// 记录输出个数
public static void permutation(char[] a, int low, int high) {
if (low == high) {
System.out.print(++count + &:&);
for (int i = 0; i &= i++) {
System.out.print(a[i]);
System.out.print(&
if (count % 5 == 0)
System.out.println();
for (int j = j &= j++) {
swap(a, j, low);
permutation(a, low + 1, high);
swap(a, j, low);
private static void swap(char a[], int c, int d) {
temp = a[c];
a[c] = a[d];
public static void main(String[] args) {
char[] words = { 'q', 'w', 's', 'c' };
permutation(words, 0, words.length - 1);
有三根杆子A，B，C。A杆上有N个(N&1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
每次只能移动一个圆盘；
大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
public static void main(String[] args) {
hannuota(3, 'A', 'B', 'C');// 从A通过B移到C
* @param n
* @param from
* @param inter
* @param to
public static void hannuota(int n, char from, char inter, char to) {
if (n == 1)
System.out.println(&disk & + n + & from & + from + & to & + to);
hannuota(n - 1, from, to, inter);
System.out.println(&disk & + n + & from & + from + & to & + to);
hannuota(n - 1, inter, from, to);
3. 斐波那契数列问题
题目：写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列定义如下：
解法一：递归，效率很低的解法
public static long Fabonacci(int n) {
if (n &= 0)
if (n == 1)
return Fabonacci(n - 1) + Fabonacci(n - 2);
}解法二：简单的迭代方法，从下往上计算，首先根据f(0)和f(1)计算出f(2),再根据f(1)和f(2)计算出f(3)……以此类推。很容易理解，时间复杂度是O(n). public static long Fabonacci1(int n) {
int[] result = { 0, 1 };
if (n & 2)
return result[n];
long currOne = 0;
long currTwo = 1;
long res = 0;
for (int i = 2; i &= ++i) {
res = currOne + currT
currOne = currT
相关题目：
1.一只青蛙一次可以跳上1级台阶，也以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
可以看做斐波那契问题。如果只有1级台阶，只有一种情况。如果有2级台阶，则有两种方法：一次是分两次跳，每次跳1级；另一种是一次跳2级。
对于一般情况，把n级台阶的跳法看成n的函数f(n)。n&2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面n-1级台阶的跳法数目，即f(n-1)；另外一种是选择第一次跳2级，此时跳法数据等于后面的n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同跳法总数是f(n)=f(n-1)+f(n-2)。
2.疯狂跳台阶：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
假设现在n=10，方法数记为f(10)。如果第一下跳了1级，那么剩下的方法为f(9)，如果第一下跳了2级，那么剩下的方法是f(8)，依次类推……，如果第一下跳了9级那么剩下的方法是f(1)，如果第一下就直接跳上10级，那么就只有一种方法。
因此，f(10)=f(9)+f(8)+f(7)+f(6)+f(5)+f(4)+f(3)+f(2)+f(1)+1；
刚开始f(1)=1，f(2)=2 &...&
3.矩形覆盖：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
假设现在是有8个2*1的小矩形去覆盖一个2*8的大矩形。我们把覆盖方法数记为f(8)。用第一个1*2的小矩形去覆盖大矩形的最左边有两个选择，竖着放或者横着放。当竖着放的时候，右边还剩下2*7的区域，这种情况下的覆盖方法是f(7)。接下来考虑横着放的情况。当用1*2的小矩形横着放在左上角的时候，左下角必须横着放一个1*2的小矩形，而在右边还剩下2*6的区域，这种情况下的覆盖方法记为f(6)。
因此f(8)=f(7)+f(6)。可以看出，这仍然是斐波那契数列。
参考来源：
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：72358次
积分：1625
积分：1625
排名：千里之外
原创：89篇
转载：15篇
评论：26条
(1)(1)(8)(27)(33)(2)(9)(17)(6)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'递归算法&&例题
递归基础练习题
1.&&求1+2+3+……+n的值
int fun(int n)
if (n == 1) return 1;
return n + fun(n-1);
void main()
printf("输入一个数用于求累加：");
&&&&&&&&&&
scanf("%d", &n);
printf("1+2+3+...+n的和为：%d\n", fun(n));
2.&&求1*2*3*……*n的值
int fun(int n)
if (n == 1) return 1;
return n * fun(n-1);
void main()
printf("输入一个数用于求累乘：");
&&&&&&&&&&
scanf("%d", &n);
printf("1*2*3*...*n的积为：%d\n", fun(n));
5.&小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？
int fun(int day)
if (day == 1) return 1;
return 2*(fun(day-1) + 1);
void main()
printf("一共有%d个桃子!!!\n", fun(10));
6.&有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？
F(N) = { IF (N == 1) RETURN 1;
IF (N == 2) RETURN 1;
RETURN F(N - 1) + F(N -2);
7.&&一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
int fun(int pos)
if (pos == 1)
&&&&&&&&&&
return 2*(fun(pos-1) + 1);
void main()
printf("一共有%d个鸭子!!!\n", fun(7));
int i, n = fun(7);
for (i = 1; i &= 7; i++) {
&&&&&&&&&&
printf("第%d天卖出的鸭子数是：%d\n", i, fun(7) - n);
&&&&&&&&&&
n = n/2 - 1;
8.&&著名的菲波拉契(Fibonacci)数列，其第一项为0，第二项为1，从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。
int Fibonacci(int n)
if (n == 1)
&&&&&&&&&&
if (n == 2) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
void main()
printf("请输入所求的n项Fibonacci数列:");
&&&&&&&&&&
scanf("%d", &n);
printf("n项的Fibonacci数列为:%d\n", Fibonacci(n));
9.&&求两个数的最大公约数。
int gcd(int n, int r)
int temp = n%r;
if (temp == 0)
&&&&&&&&&&
&&&&&&&&&&
&&&&&&&&&&
&&&&&&&&&&
gcd(n, r);
void main()
printf("请输入两个数用于求最大的公约数(用逗号分隔):");
&&&&&&&&&&
scanf("%d,%d", &n,
printf("%d和%d的最大公约数为：%d\n", n, r, gcd(n, r));
10.&&求两个数的最小公倍数。
//求两个数的最小公倍数递归算法。
#include "stdio.h"
int lcm(int s,int m,int n)
if (s%n==0)
&&&&&&&&&&
return lcm(s+m,m,n);
void main()
printf("请输入两个数用于求最小的公倍数(用逗号分隔):");
&&&&&&&&&&
scanf("%d,%d", &n,
printf("%d和%d的最小公倍数为：%d\n", n, m, lcm(n, n,
12.&&角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。
如：输入22，
输出&22&&11&&34&&17&&52&&26&&13&&40&&20&&10&&5&&16&&8&&4&&2&&1
&&&&&STEP=16
void fun(int n)
static int i = 0;
if (n == 1) {
&&&&&&&&&&
&&&&&&&&&&
printf("%d\n", n);
&&&&&&&&&&
printf("step: %d\n", i);
&&&&&&&&&&
//递归结束
&&&&&&&&&&
if (n%2 == 0) {
&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&
printf("%d&
&&&&&&&&&&&&&&&&
&&&&&&&&&&
&&&&&&&&&&
&&&&&&&&&&
&&&&&&&&&&&&&&&&
printf("%d&
&&&&&&&&&&&&&&&&
n = n * 3 + 1;
&&&&&&&&&&
//n的值已经在上面的计算中改变了，并实现了规模的减小
//知道n为1
//用递归实现循环
//printf("step: %d& ",
void main()
printf("请输入一个数用于求角谷数:");
&&&&&&&&&&
scanf("%d", &n);
13.&&将十进制转换为二进制。
void fun(int n)
int temp =
if (n == 1) {
printf("%d&
&&&&&&&&&&
&&&&&&&&&&
//n = n/2;
&&&&&&&&&&
&&&&&&&&&&
printf("%d&
", temp%2);
void main()
printf("请输入一个要转换为二进制的十进制数:");
&&&&&&&&&&
scanf("%d", &n);
15.&&梯有N阶，上楼可以一步上一阶，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。
IF (N == 1) RETURN 1;
IF (N == 2) RETURN 2;
RETURN F(N - 1) + F(N - 2);
某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况?
1、当N=1和2时，易得解～，假设F(N-1)和F(N-2)已经得到，重点分析下面的情况：2、当有N封信的时候，前面N-1封信可以有N-1或者
3、前者，对于每种错装，可从N-1封信中任意取一封和第N封错装，故=F(N-1)*(N-1)
4、后者简单，只能是没装错的那封和第N封交换信封，没装错的那封可以是前面N-1封中的任意一个，
故= F(N-2) * (N-1)
得到如下递推公式：
基本形式：d[1]=0;&&
d[2]=1递归式：d[n]= (n-1)*( d[n-1] +
有些没有写出代码！！但是给出了基本的分析！！自己写出应该不难····
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。
