C++递归函数
C++递归函数
【递归，就是在运行的过程中调用自己】
比如：（点击了下面的递归，搜索结果还是递归）
A.构成递归需具备的条件：
1.子问题须与原始问题为同样的事，且更为简单。
2.不能无限制的调用本身，必须有个出口，化简为非递归状况处理。
B.递归可以解决的问题：
阶乘、斐波那契数列、汉诺塔、杨辉三角的存取、字符串回文判断、字符串全排列、二分查找、树的深度求解
C.递归的过程（图片来源见水印，侵删）
【递归的过程可以理解为，把一个复杂的问题转化为一个个的小问题，而小问题能转化为更简单的问题，直到达到递归的“终点”——递归边界。递归边界是递归问题的特殊案例或者简单的情况，通过递归边界向上一层一层的返回数据，结束递归】
D.递归实例
Example ①：//阶乘
#include <iostream>
using namespace std;
int Leo(int n)
{
int sum = 1;
if(1 == n)//递归终止条件
{
return 1;
}
sum =n * Leo(n - 1);
return sum;//返回阶乘的总和
}
int main()
{
int num;
cin >> num;//输入一个数
cout << Leo(num) << endl; //输出该数的阶乘
return 0;
}
/*
*在求X的阶乘和时
*可以利用递归的思想
*把大问题转化成小问题
*再把小问题转化成更小的问题
*最后得解
*/Example ②：//Fibonacci数列
//Fibonacci数列的第一项为0，第二项为1，后续的每一项是前两项的和
//该数列的前两项的比例趋于一个常量：1.168...，成为黄金分割 数列形如：0 1 1 2 3 5 8 13 21 34...
#include <iostream>
using namespace std;
long int Leo(long int n);
int main()
{
long n;
cin>>n;//求Fibonacci数列的第n项
cout<<Leo(n)<<endl;
return 0;
}
long int Leo(long int n)
{
if(n==0 || n==1)
return n;
else
return Leo(n-1)+Leo(n-2);
}
Example ③：//全排列
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
公式：全排列数f(n)=n!(定义0!=1)
//无重复元素的全排列#include<bits/stdc++.h>
using namespace std;
int arr[5]={0,1,2,3,4};
int resove(int n)//递归函数
{
if(n==5)//当尝试对不存在的数组元素进行递归时，标明所有数已经排列完成，输出。
{
for(int i=0;i<5;i++)
cout<<arr[i];
cout<<endl;
return 0;
}
for(int i=n;i<5;i++)//循环实现交换和之后的全排列
{//i是从n开始 i=n; swap(arr[n],arr[i])相当于固定当前位置，在进行下一位的排列。
swap(arr[n],arr[i]);
resove(n+1);
swap(arr[n],arr[i]);
}
}
int main()
{
resove(0);
}
//输出结果
01234 01243 01324 01342 01432 01423 02134 02143 02314 02341 02431 02413 03214 03241 03124 03142 03412 03421 04231 04213 04321 04312 04132 04123 10234 10243 10324 10342 10432 10423 12034 12043 12304 12340 12430 12403 13204 13240 13024 13042 13402 13420 14230 14203 14320 14302 14032 14023 21034 21043 21304 21340 21430 21403 20134 20143 20314 20341 20431 20413 23014 23041 23104 23140 23410 23401 24031 24013 24301 24310 24130 24103 31204 31240 31024 31042 31402 31420 32104 32140 32014 32041 32401 32410 30214 30241 30124 30142 30412 30421 34201 34210 34021 34012 34102 34120 41230 41203 41320 41302 41032 41023 42130 42103 42310 42301 42031 42013 43210 43201 43120 43102 43012 43021 40231 40213 40321 40312 40132 40123//全排列算法模板
void permutation1(char* str,int sbegin,int send) //全排列的非去重递归算法
{
if( sbegin == send) //当 sbegin = send时输出
{
for(int i = 0;i <= send; i++) //输出一个排列
cout << str[i];
cout << endl;
}
else
{
for(int i = sbegin; i <= send; i++) //循环实现交换和sbegin + 1之后的全排列
{
swap(str[i],str[sbegin]); //把第i个和第sbegin进行交换
permutation1(str,sbegin + 1,send);
swap(str[i],str[sbegin]); //交换回来
}
}
} //有重复元素的全排列
【去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换】
#include <iostream>
using namespace std;
int sum=0;//记录有多少种组合
void Swap(char str[], int a, int b)
{
char temp = str[a];
str[a] = str[b];
str[b] = temp;
}
bool IsSwap(char *pchar, int nBegin, int nEnd)//判断字符是否相同
{
for (int i = nBegin; i < nEnd; i++)
if (pchar[i] == pchar[nEnd])
return false;
return true;
}
void Perm(char str[], int begin, int end)
{
if (begin==end)
{
for (int i = 0; i <= end; i++)
{
cout << str[i];
}
cout << endl;
sum++;
return;
}
else
{
for (int j = begin; j <=end; j++)
{
if (IsSwap(str, begin, j))//如果不相同 进行交换
{
Swap(str, begin, j);
Perm(str, begin + 1, end);
Swap(str, j, begin);
}
}
}
}
int main()
{
int n;
char c[16];
char tmp;
cin >> n;
tmp = getchar(); // 接受回车
if (1 <= n && n <= 15){
for (int i = 0; i < n; i++){
c[i] = getchar();
}
Perm(c, 0, n - 1);
}
cout << sum;
cout << endl;
return 0;
}有重复元素的全排列问题的关键就是要先判断是否是和后面的元素重复，如果不重复在进行交换
Example ④：//递归实现二分查找
#include<iostream>
#define MAX_SIZE 102
using namespace std;
template <class T>//类模板
int BinarySearch(T a[],const T&x,int n,int left,int right)
{
if(left>=right)
return -1;
else
{
if(a[(left+right)/2]==x)
return (left+right)/2;
else if(x>=(left+right)/2)
return BinarySearch(a,x,n,(left+right)/2+1,right);
else if(x<(left+right)/2)
return BinarySearch(a,x,n,left,(left+right)/2-1);
}
}
int main()
{
int a[MAX_SIZE];
int i,len,x,p;
cin>>len;//输入数组长度
for(i=0;i<len;i++)
cin>>a[i];
cin>>x;//输入要查找的数
p=BinarySearch(a,x,len,0,len-1);
if(p==-1)
cout<<"该数不存在！"<<endl;
else
cout<<p+1<<endl;//输出下标
return 0;
}E.递归例题
分解因数
<dl class="problem-params"> <dt> 总时间限制: </dt> <dd style="margin-left:0px;"> 1000ms </dd> <dt> 内存限制: </dt> <dd style="margin-left:0px;"> 65536kB </dd> </dl> <dl class="problem-content"> <dt style="font-size:16px;line-height:56px;"> 描述 </dt> <dd style="margin-left:0px;"> 给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * ... * an，并且1 < a1 <= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意到a = a也是一种分解。 </dd> <dt style="font-size:16px;line-height:56px;"> 输入 </dt> <dd style="margin-left:0px;"> 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (1 < a < 32768) </dd> <dt style="font-size:16px;line-height:56px;"> 输出 </dt> <dd style="margin-left:0px;"> n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数 </dd> <dt style="font-size:16px;line-height:56px;"> 样例输入 </dt> <dd style="margin-left:0px;">
2 2 20</dd> <dt style="font-size:16px;line-height:56px;"> 样例输出 </dt> <dd style="margin-left:0px;">
1 4</dd> </dl>
题目代码及分析
#include <bits/stdc++.h>
using namespace std;
int sum;//全局变量 方便在count函数中使用sum
void count(int a,int b)
{
for(int i=a;i<b;i++)
{
if(b%i==0&&i<=b/i)//如果b能整除i 且i小于商
{
sum++;
count(i,b/i);//递归计算
}
if(i>b/i) break;
}
}
int main()
{
int n;
int a; //被分解的数
cin >> n; //数据组数
while(n)
{
sum = 1;
cin >> a;
count(2,a);
cout<<sum<<endl;
n--;
}
return 0;
}
数字方格
<dl class="problem-params"> <dt> 总时间限制: </dt> <dd style="margin-left:0px;"> 1000ms </dd> <dt> 内存限制: </dt> <dd style="margin-left:0px;"> 65536kB </dd> </dl> <dl class="problem-content"> <dt style="font-size:16px;line-height:56px;"> 描述 </dt> <dd style="margin-left:0px;">
如上图，有3个方格，每个方格里面都有一个整数a1，a2，a3。已知0 <= a1, a2, a3 <= n，而且a1 + a2是2的倍数，a2 + a3是3的倍数， a1 + a2 + a3是5的倍数。你的任务是找到一组a1，a2，a3，使得a1 + a2 + a3最大。
3</dd> <dt style="font-size:16px;line-height:56px;"> 样例输出 </dt> <dd style="margin-left:0px;">
5</dd> </dl>
题目代码及分析
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int m=0;
for(int a2=n;a2>=0;a2--){//从n开始 依次向前遍历
for(int a3=n;a3>=0;a3--){
if((a2+a3)%3==0){
for(int a1=n;a1>=0;a1--){
if(((a1+a2+a3)%5==0) && ((a1+a2)%2==0)){
m=max(m,a1+a2+a3);//求出最大值 输出
}
}
}
}
}
cout<<m;
return 0;
}F.心得体会
在做递归的题目时，不要纠结于小细节，要整体把握，只要是递归边界正确，递归方法正确就可以，不要太在意是怎么运作的。太在乎细节，反而不利于题目的求解。
