递归函数及例题

定义：
一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的 。
古典递归函数，是一种定义在自然数集合上的函数，它的未知值往往要通过有限次运算回归到已知值来求出，故称为“递归”。它是古典递归函数论的研究对象 。
条件：
1 递归出口即结束条件；
2 递推关系；
例题1：求任意正整数的逆置数
示例1：
输入：
890

输出

解题思路：
1 递归出口： n=0时可结束
2 递推关系： 使用变量flag标记是否是最后一位数。如果最后一位数是0，则不输出，直接再次调用int_inverts(n/10,flag)函数。如果不是，修改flag的值，先输出，然后在调用int_inverts(n/10,flag)。
参考代码：

#include  
     #include  
     #include  
     using namespace std; //求正整数的逆置数 //递归求 //结束条件： //递推关系： void int_inverts(int n,int flag) { 
    if(n == 0) return ; if(n%10 == 0 &&flag == 0) { 
    int_inverts(n/10,flag); } else { 
    flag =1; cout<<n%10; int_inverts(n/10,flag); } } int main() { 
    int n; cin>>n; int_inverts(n,0); cout<<endl; } 

例题2：求最大公约数
题目描述
设计递归函数;计算正整数a和b的最大公约数并返回
输入与输出要求：
输入两个正整数a和b，输出两数的最大公约数数，占一行。

Sample 1：

Sample 2：

解题思路：
利用辗转相除法可知，当n%m!=0时，就一直计算（m,n%m）的最大公约数。可知
递归出口： n%m == 0 ,返回m;
递推关系： divisor(n,m) = divisor(m,n%m),当n%m != 0时；

参考代码：

#include  
     #include  
     #include  
     using namespace std; //求最大公约数 int divisor(int n,int m) { 
    if(n%m == 0) return m; return divisor(m,n%m); } int main() { 
    int n,m; cin>>n>>m; cout<<divisor(n,m)<<endl; return 0; } 

例题3：二进制转十进制数
问题描述：

#include  
     #include  
     #include  
     #include  
     using namespace std; //二进制数转十进制 int b_shift_d(int n) { 
    if(n == 0 || n == 1) return n; else { 
    return n%10+b_shift_d(n/10)*2; } } int main() { 
    int n; cin>>n; cout<<b_shift_d(n)<<endl; return 0; } 

例题4： 素数分解
问题描述：
素数，又称质数，是指除 1和其自身之外，没有其他约数的正整数。例如 2、3、5、13 都是质 数，而 4、9、12、18 则不是。 虽然素数不能分解成除 1和其自身之外整数的乘积，但却可以分解成更多素数的和。你需要编程 求出一个正整数最多能分解成多少个互不相同的素数的和。 例如，21 = 2 + 19 是 21的合法分解方法。21 = 2 + 3 + 5 + 11 则是分解为最多素数的方法。
输入 n (10 ≤ n ≤ 200)。
输出 n 最多能分解成多少个不同的素数的和。

样例1,

样例2,

解题思路：
先设置num[]数组来存储小于n的所有素数。其次，index即元素的下标，sum即元素之和，total为已经选择的元素的个数，作为递归函数的参数参与。可采用两种写法：
如下所示：
第一种：

int total = 0； void find_longest(int index,int sum,int n) { 
    if(sum == n ) { 
    if(longest < total) longest = total ; return ; } if(sum > n || index >= top) return ; total++; find_longest(index+1,sum+num[index],n); total--; find_longest(index+1,sum,n); } 

第二种：

void find_longest(int index,int sum,int total,int n) { 
    if(sum == n ) { 
    if(longest < total) longest = total ; return ; } if(sum > n || index >= top) return ; find_longest(index+1,sum+num[index],total+1,n); find_longest(index+1,sum,total,n); } 

参考代码：

#include  
     #include  
     #include  
     #include  
     using namespace std; //素数分解 /* 递归出口设定： 递推关系： */ int top=0; int num[201]; int longest; int is_prime(int n) { 
    if(n == 1) return 0; if(n == 2) return 1; for(int i=2;i<n;i++) { 
    if(n%i == 0) { 
    return 0; break; } } return 1; } void find_longest(int index,int sum,int total,int n) { 
    if(sum == n ) { 
    if(longest < total) longest = total ; return ; } if(sum > n || index >= top) return ; find_longest(index+1,sum+num[index],total+1,n); find_longest(index+1,sum,total,n); } int main() { 
    int n; cin>>n; for(int i=1;i<=n;i++) { 
    if(is_prime(i)) num[top++] = i; } longest = 0; find_longest(0,0,0,n); cout<<longest<<endl; return 0; } 

问题5：汉诺塔问题
题目描述：
n个圆盘从下面开始按大小顺序摆放在A柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘，求最少的移动步骤。

解题思路： （在链接中）
汉诺塔问题解题思路及代码

问题6：全排列问题：
对于给定的集合A{a1,a2,…,an},其中的n个元素互不相同，如何输出这n个元素的所有排列（全排列）。
解题思路：
全排列问题解题思路及代码

问题7： 整数划分问题：
问题描述：
整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数n写成如下形式：