（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第8讲 递归

学科竞赛编程 C++ NOIP NOI IOI 1 1 PART ONE 递归概念 庙里有个老和尚给小和尚讲故事 庙里有个老和尚给小和尚讲故事 从前有座山，山里有座庙 从前有座山，山里有座庙 很久以前，有一则古老而有趣的故事流传至今： 1 PART ONE 递归概念 你会发现甲镜子里有乙镜子的像，乙镜子里有甲镜子的像。而且反反复复，就会产生一连串的“像中像” 当你站在甲、乙两面相互面对面的镜子中间时，你会发现什么奇妙的现象吗？ 1 PART ONE 递归算法 操作特点： （1）每一步执行动作一样； （2）每调用一次规模缩小； （3）结果通过一步步层层退出。 两种情况： 函数自己调用自己 两个函数之间的相互调用 其他条件：有递归边界 递归算法：就是一种函数直接或间接地调用自身的算法 1 2 3 4 1 PART ONE 递归算法 void story() { cout<<“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事，他讲的故事是：”; getchar();//按任意按键听下一个故事 story();//调用自身函数 } 由经典故事到程序设计 问题：程序陷入死循环，故事一直重复，请想一想，如何跳出死循环吧！ 提示：定义一个变量，限定故事函数story()的循环次数 1 PART ONE 递归的执行过程 问第5个学生多少岁？他说比第4个学生大2岁 问第4个学生岁数，他说比第3个学生大2岁 问第3个学生，又说比第2个学生大2岁 问第2个学生，说比第1个学生大2岁 最后问第1个学生，他说是10岁 学生年龄问题 有5个学生坐在一起 请问第5个学生多大？ 1 PART ONE 解题思路： 要求第五个年龄，就必须先知道第四个年龄， 要求第四个年龄，就必须先知道第三个年龄， 要求第三个年龄，就必须先知道第二个年龄， 要求第二个年龄，就必须先知道第一个年龄， 每个年龄都比其前1个学生的年龄大2 递归的执行过程 age(5)=age(4)+2 age(4)=age(3)+2 age(3)=age(2)+2 age(2)=age(1)+2 递推阶段 age(1)=10 回溯阶段 age(2)=12 age(2)=14 age(2)=16 age(2)=18 递归剖析 1 2 1 PART ONE 递归的执行过程 int age(int n){ int c; if(n==1) {c=10;} else {c=age(n-1)+2;} return c;} int main() { cout<<age(5); retrun 0; } 算法设计 1 PART ONE 递归的应用 Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”引出的 一对兔子，从出生满2月起，每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假如兔子都不死，请问第1个月出生的一对兔子，第n个月有几只兔子？ 还记得Fibonacci数列的递推公式吗？请你写出公式及边界条件吧！ 请思考：如何用递归方法实现Fibonacci数列 Fibonacci数列 1 PART ONE 递归的应用 #include <iostream> using namespace std; int main() {int a[1000],n; cin>>n; a[0]=a[1]=1; for(int i=2; i<=n; i++){a[i]=a[i-1]+a[i-2];} cout<<a[n]; return 0;} 递推算法 请你写出递归的实现方法吧 #include <iostream> using namespace std; int fib(int n){ if(n==0){return 0;} if(n==1){return 1;} else{return fib(n-1)+fib(n-2);}} int main() {int n; cin>>n; cout<<fib(n); return 0;} 1 PART ONE 递归的应用 Hanoi塔问题 还记得Hanoi塔的递推公式吗？请你写出公式及边界条件吧！ 请思考：如何用递归方法实现Hanoi塔 1 PART ONE 递归的应用 #include <iostream> using namespace std; void move(int n, char X, char Z, char Y){ //如果n=0，则退出，即结束程序 if(n==0){return;} //用Z柱作为协助过渡，将X柱上的n-1片移动到Y柱上 move(n-1, X, Y, Z); k++;//统计需要移动的次数 cout<<k<<“:”<<X<<“-”<<Z<<endl; /