递归函数及例题_递归树求解递归式例题
大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说递归函数及例题_递归树求解递归式例题,希望能够帮助大家进步!!!
定义：
一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的 。
古典递归函数，是一种定义在自然数集合上的函数，它的未知值往往要通过有限次运算回归到已知值来求出，故称为“递归”。它是古典递归函数论的研究对象 。
条件：
1 递归出口即结束条件；
2 递推关系；
例题1：求任意正整数的逆置数
示例1：
输入：
890
输出
解题思路：
1 递归出口： n=0时可结束
2 递推关系： 使用变量flag标记是否是最后一位数。如果最后一位数是0，则不输出，直接再次调用int_inverts(n/10,flag)函数。如果不是，修改flag的值，先输出，然后在调用int_inverts(n/10,flag)。
参考代码：
#include <iostream>
#include <bits/stdc++.h>
#include <string>
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时；
参考代码：
此代码由Java架构师必看网-架构君整理
#include <iostream>
#include <bits/stdc++.h>
#include <string>
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：二进制转十进制数
问题描述：
输入一个整数n，代表二进制数，其长度不大于10，输出转换后的十进制数，占一行。
解题思路：
递归出口： n=1或n=0 , 直接返回值n；
地推关系： b_shift_d(n) = n%10 + 2*b_shift_d(n/10);
示例1：
示例2：
参考代码：
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
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为已经选择的元素的个数，作为递归函数的参数参与。可采用两种写法：
如下所示：
第一种：
此代码由Java架构师必看网-架构君整理
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 <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
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写成如下形式：
n=m1+m2+…+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,…,mi}为n的一个划分。
1
正整数6有如下11种不同的划分，所以P(6)=11。
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1
解题思路：
今天文章到此就结束了，感谢您的阅读，Java架构师必看祝您升职加薪，年年好运。
腾讯云开发者
