第16课 递归

递归的数学模型其实就是 数学归纳法，这个在高中的数列里面是最常用的，下面介绍一下数学归纳法。

数学归纳法适用于将解决的原问题转化为解决它的子问题，而它的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是归纳结束的那一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷归纳了。

总的来说，归纳法主要包含以下三个关键要素：

步进表达式：问题蜕变成子问题的表达式；
结束条件（边界条件）：什么时候可以不再使用步进表达式；
直接求解表达式（边界值计算方法）：在结束条件下能够直接计算返回值的表达式。
事实上，这也正是某些数学中的数列问题在利用编程的方式去解决时，可以使用递归的原因，比如著名的斐波那契数列问题。

Q1.累加计算

首先看一个最简单的累加计算问题：用递归的方法求1+2+3+……+N的值。

1、步进表达式：将求1到N的和描述为sum(n)，按照数学归纳法，变成解决子问题的形式 sum(n)=n+sum(n-1);
2、结束条件：n=1时，sum(1)=1，因为没有必要再写成sum(1)=0+sum(0)了。
3、找到结束条件n=1，也就是我们常说的边界条件，没有它就会进入死循环了。我们总结出累加问题的递归表达式是：
sum(n)=1;             (n==1)
sum(n)=n+sum(n-1);    (n>1)

写出函数：

int sum(int n){
	if(n==1){                         //边界条件
		return 1;
	}else{
		return n+sum(n-1);        //递归
	}
}

Q2.斐波那契数列

int f(int n){
	if(n==1){       //第1项和第2项数据是边界
		return 0;
	}else if(n==2){
		return 1;       
	}else{
		return f(n-1)+f(n-2);              //第n项数据=第n-1项+第n-2项
	}
}

Q3.倒序数

分析：要从低位往高位倒序输出n，使用n%10输出，然后将n/10得到新的n。边界条件是：n<10，直接输出n。

Q4.转进制

用递归算法将一个十进制数X转换成任意进制数M（M≤16）。

分析：观察用短除法实现十进制转换成任意进制数的方法，找到递归表达式和边界条件。

void print(int n){
	if(n<10){
		cout<<n;
	}else{
		switch(n){             //超过10进制的数，要用字母输出
			case 10:cout<<'A';break;
			case 11:cout<<'B';break;
			case 12:cout<<'C';break;
			case 13:cout<<'D';break;
			case 14:cout<<'E';break;
			case 15:cout<<'F';break;
		}
	}	
}

void turn(int n,int B){        //将n转换成B进制数字
	if(n>=0&&n<B){            //边界条件是n小于B
		print(n);
	}else{
		turn(n/B,B);     //更小规模的问题是将n/B转换成B进制数字
		print(n%B);      //输出n除以B的余数
	}
}

Q5.字符串逆序

void rprint(char a[],int n){
	if(a[n]!='\0'&&a[n]!='!'){     //输出下标n的值
		cout<<a[n];
	}
	
	if(n>0){
		rprint(a,n-1);        //更小规模问题是输出长度是n-1的字符数组
	}
}