【项目-用递归方法求解】
（1）编写递归函数求出n的阶乘（自定义main函数，调用定义的递归函数）
参考解答：
#include <iostream>
using namespace std;
long fact(int); //函数声明
int main( )
{
int n; //n为需要求阶乘的整数
long y; //y为存放n!的变量
cout<<"please input an integer ："; //输入的提示
cin>>n; //输入n
y=fact(n); //调用fac函数以求n!
cout<<n<<"!="<<y<<endl; //输出n!的值
return 0;
}
long fact(int n) //递归函数
{
long f;
if (n==0) f=1; //0!和1!的值为1
else f=fact(n-1)*n; //n>1时，进行递归调用
return f; //将f的值作为函数值返回
}
（2）写出求1*3*...*n的递归式，并编写出递归函数求解。
参考解答：
#include <iostream>
using namespace std;
long f(int);
int main( )
{
int n;
long y;
cout<<"请输入一个数 ：";
cin>>n;
if(n%2) //若奇数
y=f(n);
else
y=f(n-1);
cout<<n<<"以内的奇数积是:"<<y<<endl;
return 0;
}
long f(int n)
{
long s;
if (n==1)
s=1;
else
s=f(n-2)*n;
return s;
}
（3）编程序，用递归函数求出两个数的最大公约数。（包括编main函数，调用定义的递归函数）
参考解答：
//递归解法
#include "iostream"
using namespace std;
int gcd(int x, int y);
void main()
{
int m,n;
cout<<"输入两个数字:";
cin>>m>>n;
cout<<"最大公约数:";
cout<<gcd(m,n)<<endl;
}
int gcd(int a, int b)
{
int t,g;
//if (a < b) t=a,a=b,b=t; //无所谓大小
if (b==0)
g=a;
else
g=gcd(b,a%b);
return g;
}
（4）编制递归函数fib(int n)返回第n个Fibnacci数，以此输出Fibnacci序列的第20个数。
参考解答：
//递归法
#include <iostream>
using namespace std;
int fib(int n);
int main()
{
cout<<fib(20)<<endl;
return 0;
}
//返回Fibnacci序列中的第n个数
int fib(int n)
{
if(n==1)
return 0;
else if(n==2)
return 1;
else
return(fib(n-1)+fib(n-2));
}
（5）输入一个整数n，要求输出对应的二进制形式，请用递归函数实现。
参考解答：
#include <iostream>
using namespace std;
void dec2bin(int n);
int main()
{
int n;
cout<<"请输入一个整数：";
cin>>n;
cout<<n<<"对应的二进制形式为：";
dec2bin(n);
cout<<endl;
return 0;
}
void dec2bin(int n)
{
if(n==0)
return; //其实在此有个BUG，如果在main()中直接调用的是dec2bin(0)，并不会输出其二进制形式0，请在评论中跟进如何处理
else
{
dec2bin(n/2);
cout<<n%2;
return;
}
}
提示：二进制整数n转换为二进制的方法是“除2取余法”，即将n除以2后得到的余数，由后到前“串”起来，得到对应的二进制数，如图。
（6）汉诺塔
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，下面左图给出了移动方法的提示。请编制递归函数输出盘子数为4时（程序调试后，试试15个、20个，直至64个，看看会如何），移动的方案。图为盘子数为3时的输出供参考。
参考解答：
#include <iostream>
using namespace std;
const int discCount=3;
void move(int, char, char,char);
int main()
{
move(discCount,'A','B','C');
return 0;
}
void move(int n, char A, char B,char C)
{
if(n==1)
{
cout<<A<<"-->"<<C<<endl;
return;
}
else
{
move(n-1,A,C,B);
cout<<A<<"-->"<<C<<endl;
move(n-1,B,A,C);
return;
}
}
下面的解答还可以输出移动的次数，当盘子数太多时，这是个温柔长的过程：
//输出且计数
#include <iostream>
using namespace std;
const int discCount=3;
long move(int, char, char,char);
int main()
{
long count;
count=move(discCount,'A','B','C');
cout<<discCount<<"个盘子需要移动"<<count<<"次。"<<endl;
return 0;
}
long move(int n, char A, char B,char C)
{
long c1,c2;
if(n==1)
{
cout<<A<<"-->"<<C<<endl;
return 1;
}
else
{
c1=move(n-1,A,C,B);
cout<<A<<"-->"<<C<<endl;
c2=move(n-1,B,A,C);
return c1+c2+1;
}
}
下面的代码不去输出移动方案，仅输出需要移动的次数，免去了输出花费的时间：
//仅计数
#include <iostream>
using namespace std;
const int discCount=3;
long move(int, char, char,char);
int main()
{
long count;
count=move(discCount,'A','B','C');
cout<<discCount<<"个盘子需要移动"<<count<<"次。"<<endl;
return 0;
}
long move(int n, char A, char B,char C)
{
long c1,c2;
if(n==1)
{
return 1;
}
else
{
c1=move(n-1,A,C,B);
c2=move(n-1,B,A,C);
return c1+c2+1;
}
}
有同学的输出中，加入了“几号盘子”字样，输出信息更明白：
#include <iostream>
using namespace std;
void move(int n, char A, char B,char C);//盘子数由序号数增大而依次增大
int main()
{
move(4,'A','B','C');
return 0;
}
//有n个盘子，
void move(int n, char A, char B,char C)
{
if(n==1)
{
cout<<n<<"号盘子："<<A<<" to "<<C<<endl;
}
else
{
move(n-1,A,C,B);
cout<<n<<"号盘子："<<A<<" to "<<C<<endl;
move(n-1,B,A,C);
}
}
