递归是一种解决问题的方法，将问题分解为更小的子问题，直到得到一个足够小的问题可以被很简单的解决。通常递归涉及函数调用自身。递归允许我们编写优雅的解决方案，解决可能很难编程的问题。
例如，要求一个列表中所有数字的和，用循环可以写出以下代码：
def listsum(numList): theSum = 0 for i in numList: theSum += i return theSum print(listSum([1, 3, 5, 7, 9])
用循环解决的思路是((((1+3)+5)+7)+9)，我们知道加法有结合律，所以也可以这样求：(1+(3+(5+(7+(9)))))，这样做的目的是先将问题层层分解，直到分解成一个数字求和这样的简单问题，再从最内层将答案返回，拼凑出最初的问题的答案。递归方法的代码如下：
def listsum(numList):
if len(numList) == 1:
return numList[0]
else:
return numList[0]+listsum(numList[1:])
print(listsum([1, 3, 5, 7, 9]))
以上面这个问题为例，提出递归的三个定律：
1、 递归算法必须具有基本情况
基本情况是停止递归的条件，通常足够小以至于可以直接求解，比如列表求和问题中长度为1的列表。
2、递归算法必须改变其状态并向基本情况靠近
在调用函数的过程中，函数的使用的数据要向基本情况靠拢，在上述问题中基本情况是长度为1的列表，所以朝向基本情况的自然进展是缩短列表，使用numList[1:]生成一个更短的列表。
3、递归算的必须以递归方式调用自身
递归算法必须调用自身，这是由递归的定义决定的。
接下来就是用上面着三个原则解决经典的递归问题了，算法与语言关系不大，思路都是一样的，博主只会python和C++，就用这两种语言随机写了。
例1：将整数转换为任意进制（2-16）字符串
定义一个序列convString = ‘0123456789ABCDEF’
1、考虑基本情况，当将一个数a转化为b进制字符串，如果a
def toStr(n,base):
converString = '0123456789ABCDEF'
if(n
例2：汉诺塔游戏
这是一个很经典的问题，所以问题描述就不写了，直接开始分析。原始塔称为A，中间塔称为B，目标塔称为C。
1、考虑基础情况，A塔只有一个盘，那么只需A->C一步就可以完成。
2、考虑向基本情况靠近，要想将n个盘子借助B从A移到C就需要先将n-1个盘子借助C从A移到B，再将A上剩的最后一个盘子移到C，最后再借助A将B上的n-1个盘子移到C。
按照上面的描述就可以写出程序，打印出移动盘子的顺序。
def moveTower(height, fromPole, toPole, withPole):
if height >= 1:
moveTower(height-1, fromPole, withPole, toPole)
print("moving disk from", fromPole, "to", toPole)
moveTower(height-1, withPole, toPole, fromPole)
moveTower(3, "A", "C", "B")
# include
using namespace std;
void moveTower(int height, char fromPole, char toPole, char withPole){
if (height>=1){
moveTower(height-1, fromPole, withPole, toPole);
cout << "moving disk from "<
例3：n皇后问题
在国际象棋中，两个皇后若位于棋盘的同行、同列或同对角线上就会相互攻击。n皇后问题就是要求将n个皇后摆在n*n的棋盘上，且皇后之间不能相互攻击。
1、考虑基本情况，很明显，一行只能摆一个皇后，我们从第一行开始摆，当摆完第n行时就返回，这就是一个基本情况。
2、考虑向基本情况靠近，很简单，每摆好一行，行数就+1，直到行数=n。
N = 8 # 八皇后问题
queenPos = [0]*N # 存放摆好的皇后的位置
def NQueen(k): # 在0~k-1行的皇后摆好的情况下，摆第k行的皇后
if k == N: # 说明所有的皇后都已经摆完
for i in range(N):
print(queenPos[i]+1, end = ' ') # 输出在每一行的第几列上摆皇后（从1开始）
print("n")
return # 输出的每一行代表一种摆法，第i个数字为j表示在第i行第j个位置摆上皇后
for i in range(N): # 逐次尝试第k个皇后的位置
chongtu = False
for j in range(k): # 逐次查看第i列的位置是否和前面的皇后冲突
if queenPos[j] == i or abs(j-k)==abs(queenPos[j]-i): # 如果和第j行的皇后冲突
chongtu = True
break # 不用继续判断和其他的皇后冲不冲突了，直接检查下一个位置
if chongtu==False: # 如果没有冲突的
queenPos[k] = i # 确定位置
NQueen(k+1) # 再去摆下一行的皇后
NQueen(0) # 从第0行开始摆皇后
例4：波兰（前缀）表达式求值
我们日常使用的表达式是中缀表达式，即运算符在数字的中间，这就需要运算具有优先级，并用小括号去改变运算顺序。波兰表达式就是前缀表达式，即运算符在要计算的数字前面，比如(2+3)x4的波兰表达式为x + 2 3 4，波兰表达式的计算没有优先级，也没有小括号，只需要遵循运算符在两个参与运算的数字前面（紧挨着）的规则就可以了。
1、思考基本情况，当波兰表达式只有一个数字时，直接就可以得到结果。
2、考虑向基本情况靠近，当遇到运算符号时，就表示有两个波兰表达式需要计算，再分别计算这两个波兰表达式，直到要计算的波兰表达式只有一个数字。
# include
# include
# include
using namespace std;
double exp(){
char s[20];
cin>>s;
switch (s[0])
{
case '+': return exp()+exp();
case '-': return exp()-exp();
case '*': return exp()*exp();
case '/': return exp()/exp();
default: return atof(s); // atof()将字符串转换成浮点型数
break;
}
}
int main(){
printf("%1f", exp());
return 0;
}
例5、中缀表达式求值
和波兰表达式求值相比，中缀表达式求值更加复杂，因为要考虑小括号和运算顺序。
1、基本情况也是只有一个数字的表达式。
2、拆解用运算符号连接的表达式，直到只剩一个数字。
需要注意的是，在中缀表达式中要先算乘除，所以设定表达式、项、因子，这三个概念方便理解。他们之间的关系如下：
# include
# include
# include
using namespace std;
// 问题本身就是用递归定义的
int factor_value(); // 因子
int term_value(); // 项
int expression_value(); // 表达式
int main()
{
cout << expression_value() << endl;
return 0;
}
int expression_value() { // 求一个表达式的值
int result = term_value(); // 求第一项的值
bool more = true;
while (more) {
char op = cin.peek(); // 看一个字符，不取走
if (op == '+' || op == '-') {
// 如果是+-，说明后面还有项
cin.get(); // 从输入中取走一个字符
int value = term_value(); // 计算项的值
if (op == '+') result += value;
else result -= value;
}
else more = false;
}
return result;
}
int term_value() {// 求一个项的值
int result = factor_value(); // 求第一个因子的值
while (true) {
char op = cin.peek();
if (op == '*' || op == '/') {
cin.get();
int value = factor_value();
if (op == '*') result *= value;
else result /= value;
}
else
break;
}
return result;
}
int factor_value() { // 求一个因子的值
int result = 0;
char c = cin.peek();
if (c == '(') {
cin.get();
result = expression_value();
cin.get();
}
else {
while (isdigit(c)) {
result = 10 * result + c - '0';
cin.get();
c = cin.peek();
}
}
return result;
}
例6、爬楼梯
输入楼梯的级数n，每次可以爬一层或者两层，输出有几种不同的爬法。
1、考虑边界条件，n=0有1种爬法，n=1有1种爬法，n=2有2种爬法。
2、向边界条件靠近，n个台阶可以先爬一个，也可以先爬两个，f(n)=f(n-1)+f(n-2)。
# include
using namespace std;
int N;
int stairs(int n){
if (n==0)
return 1;
if(n==1)
return 1;
if(n==2)
return 2;
return stairs(n-1) + stairs(n-2);
}
int main(){
while (cin>>N){
cout<
例7、摆苹果
把M个同样的苹果放到N个同样的盘子里，允许有空着的盘子，问有几种放法。5，1，1和1，5，1是同一种放法。
设把i个苹果放到k个盘子有f(i, k)种放法。
1、考虑边界情况，f(<=0, )=1，f( , <=0)=0。
2、向边界情况靠近：
（1）i>=k，苹果比盘子多（或者一样多），有两大种放法，第一种是每个盘子都有苹果的放法，先给每个盘子都放一个，有f(i-k, k)种放法。第二种是有空的盘子，有f(i, k-1)种放法。
（2）i
# include
using namespace std;
int apple(int i, int k){
if(i>i>>k){
cout<
例8、算24
输入四个小于10的正整数，输出这四个数是否能够通过加减乘除得到结果24，可以使用小括号。
1、边界条件，若是一个数计算24，只需要判断这个数是不是24就可以了。
2、向边界情况靠近，n个数算24，总有两个数要先参与运算，剩下n-2个数，这样就变成了n-1个数算24。
# include
# include
using namespace std;
double a[5];
# define EPS 1e-6
bool isZero(double x){
return fabs(x)<=EPS;
}
bool suan24(double a[], int n){ //用数组里的n个数计算24
if(n==1){
if(isZero(a[0]-24))
return true;
else
return false;
}
double b[5];
for(int i=0;i>a[i];
if(suan24(a, 4))
cout<<"yes"<
总结
递归有三大作用：
（1）替代多种循环。本文的引例计算列表中的数字之和，例1转换进制就是这种情况，这种问题可以用递归解决也可以用单层循环解决，比较简单。例3的n皇后问题也可以用循环解决，但是需要n重循环，当n比较大的时候就很不方便，这时候就需要用递归代替多重循环。
（2）解决本来就是用递归形式定义的问题。本文的例4前缀表达式和例5中缀表达式的计算就是用递归形式定义的问题。
（3）将问题分解为规模更小的子问题进行求解。这种情况是最多的，可以将很多问题简单化，当面对一个复杂问题时，不妨考虑将其拆解，套用递归的两个特点，看是否能用递归解决。本文中的例2汉诺塔、例6爬楼梯、例7摆苹果、例8算24都是这种情况。
