C++编程-递归算法1

先言

关于递归算法

例题一

题目描述

算法分析

标准程序

代码分析

例题二

题目描述

算法分析

标准程序

例题三

题目描述

算法分析

标准程序

代码分析

例题四

题目描述

标准程序

代码分析

后言

先言

从今天开始，我们将新的算法——递归，比递推难度大，所以请认真学习

关于递归算法

前面已经介绍了关于递归调用这样一种操作，而递归程序设计是C++语言程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易解决了。递归特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。

例题一

题目描述

给定n（n>=1）,用递归的方法计算1+2+3+4+...+(n-1)+n。

算法分析

本题可以用递归方法求解，其原因在于它符合递归的三个条件：

(1)本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n;

(2)给定n,所以是有限次的递归调用；

(3)结束条件是当n=1，则s=1。

标准程序

#include<iostream>
using namespace std;
int fac(int);                                    //递归函数
int main()
{int t;cin>>t;                                   //输入t的值cout<<"s="<<fac(t)<<endl; //计算1到t的累加和，输出结果
}
int fac(int n)
{if (n==1) return 1;return (fac(n-1)+n);              //调用下一层递归
}

代码分析

运行程序，当T=5时，输出结果：S=15，其递归调用执行过程是：（设T=3）

递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部都有用特殊的管理方法——栈（先进后出）来管理，一旦递归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。

例题二

题目描述

设有N个数已经按从大到小的顺序排列，现在输入X，判断它是否在这N个数中，如果存在则输出：“YES” 否则输出“NO”。

算法分析

该问题属于数据的查找问题，数据查找有多种方法，通常方法是：顺序查找和二分查找，当N个数排好序时，用二分查找方法速度大大加快。二分查找算法：

（1）设有N个数，存放在A数组中，待查找数为X，用L指向数据的高端，用R指向数据的低端，MID指向中间：

（2）若X=A[MID] 输出 “YES”；

（3）若X<A[MID]则到数据后半段查找：R不变，L=MID+1，计算新的MID值，并进行新的一段查找；

（4）若X>A[MID]则到数据前半段查找：L不变，R=MID-1，计算新的MID值，并进行新的一段查找；

（5）若L>R都没有查找到，则输出“NO”。

该算法符合递归程序设计的基本规律，可以用递归方法设计。

标准程序

#include<iostream>
#include<cstdlib>
using namespace std;
int a[11];
void search(int x,int top,int bot)                            //二分查找递归过程
{int mid; if (top<=bot){mid=(top+bot)/2;                                     //求中间数的位置if (x==a[mid])  cout<<“YES”<<endl;  //找到就输出else if (x<a[mid]) search(x,mid+1,bot);     //判断在前半段还是后半段查找else search(x,top,mid-1);}  else cout<<"NO"<<endl;}
int main()                                             //主程序
{int k,x,L=1,R=10;cout<<"输入10个从大到小顺序的数："<<endl;for (k=1;k<=10;k++) cin>>a[k];cin>>x;search(x,L,R); 
}

例题三

题目描述

有N个圆盘，依半径大小（半径都不同），自下而上套在A柱上，每次只允许移动最上面一个盘子到另外的柱子上去（除A柱外，还有B柱和C柱，开始时这两个柱子上无盘子），但绝不允许发生柱子上出现大盘子在上，小盘子在下的情况，现要求设计将A柱子上N个盘子搬移到C柱去的方法。

算法分析

本题是典型的递归程序设计题。

(1)当N=1 时，只有一个盘子，只需要移动一次:A—>C;

(2)当N=2时，则需要移动三次：

A---- 1 ----> B, A ---- 2 ----> C, B ---- 1----> C.

(3)如果N=3，则具体移动步骤为：

假设把第3步，第4步，第7步抽出来就相当于N=2的情况（把上面2片捆在一起，视为一片）：

所以可按“N=2”的移动步骤设计：

①如果N=0，则退出，即结束程序;否则继续往下执行;

②用C柱作为协助过渡，将A柱上的（n-1）片移到B柱上，调用过程mov(n-1, a,b,c);

③将A柱上剩下的一片直接移到C柱上;

④用A柱作为协助过渡，将B柱上的（n-1）移到C柱上，调用过程mov (n-1,b,c,a)。

标准程序

#include<iostream>
using namespace std;
int k=0,n;
void mov(int n,char a,char c,char b) 
//用b柱作为协助过渡，将a柱上的（n）移到c柱上
{if (n==0) return;        //如果n=0，则退出，即结束程序mov(n-1,a,b,c );        //用c柱作为协助过渡，将a柱上的（n-1）片移到b柱上k++;cout <<k<<" :from "<<a <<"-->"<<c<<endl; //超时改scanf和printfmov(n-1,b,c,a );        //用a柱作为协助过渡，将b柱上的（n-1）移到c柱上
}
int main()                                        
{cout<<"n=";cin>>n;mov(n,'a','c','b'); 
}

代码分析

程序定义了把n片从A柱移到C柱的过程mov (n,a,c,b)，这个过程把移动分为以下三步来进行：

①先调用过程mov(n-1, a, b, c)，把(n-1)片从A柱移到B柱, C柱作为过渡柱;

②直接执行 cout(a, ’--＞’, c)，把A柱上剩下的一片直接移到C柱上，;

③调用mov(n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。

对于B柱上的(n-1)片如何移到C柱，仍然调用上述的三步。只是把(n-1)当成了n，每调用一次，要移到目标柱上的片数N就减少了一片，直至减少到n=0时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。

mov过程中出现了自己调用自己的情况，在C++中称为递归调用，这是C++语言的一个特色。对于没有递归调用功能的程序设计语言，则需要将递归过程重新设计为非递归过程的程序。

例题四

题目描述

用递归的方法求斐波那契数列中的第N个数

标准程序

#include<iostream>
using namespace std;
int a[11];
int fib(int);
int main()
{int m;cin>>m;                              cout<<"fib("<<m<<")="<<fib(m);          
}
int fib(int n)
{if (n==0) return 0;                         //满足边界条件，递归返回if (n==1) return 1;                         //满足边界条件，递归返回return (fib(n-1)+fib(n-2));             //递归公式，进一步递归
}