对递归的一些感悟

简要的概念

递归真的是一个很神奇的概念。
简单来说，递归就是函数不断地打开自己，直到遇到一个明确的指令（可以理解为出口）得到一个明确的返回值，从最后一层不断返回，被打开的函数，随着返回值的传入而关闭。最终，该递归函数将得到一个明确的值。
这只是递归的概念，在我看来，递归可以总结为“大事化小，小事化了”。

递归与数学归纳法

事实上，递归就是数归在程序中的体现。
用递归，首先要解决两个问题。

1. 递归表达式（即前一项与后一项的关系）
2. 递归出口（表达式再好也是抽象的，有出口才能停下，才有结果）。

解决这两个问题后，就可以去写程序了
不要想概念中不断调用的过程，不然，你会吐的。
只要明确递归功能，并且保证递归可以进行到出口即可。

如计算一个整型数组之和：

# include<stdio.h>

int sum(int arr[], int n);
int main(void){
    
	int arr[5] = {
    1,2,3,4,5};  //递归表达式：sum(arr,n) = sum(arr,n-1) + arr[n]
							   //递归出口：arr[0] = 1;
	int result = sum(arr,4);
	printf("sum = %d",result);

	getchar();					//便于看到输出结果。
	return 0;
}
int sum(int arr[], int n){
    
	if(n == 0){
    					//判断出口
		return arr[0];
	}else{
    
		return sum(arr,n-1) + arr[n]; 	//执行递归
	}
}

递归和循环

其实，如果题目没有明确要求用递归解题，我们大部分同学想到的应该是循环。
因为，递归实现过程中，很多步骤都用着相同的方法。这和我们最开始学的循环很契和。
但他们很不同。

1. 首先，在内存中，循环结构在同一个储存空间内不断进行。而递归在不断调用自己的同时，原先 的函数并没有终止，递归所占用的空间是十分恐怖的。
2. 对于循环，递归皆可以实现。而对于递归，循环有时候无可奈何，如汉诺塔问题。

//相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、
//B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆
//上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘
//在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
#include<stdio.h>

void hanoi(int n,char a,char b,char c){
    			//递归功能：解决n块铜板的汉诺塔问题。起始柱A、
												//辅助柱B及目标柱C
	if(n == 1){
    						//出口
		printf("%c->%c\n",a,c);
	}else{
    
		hanoi(n-1,a,c,b);			//如果大于一块，可以先将最下层上的n-1块铜板当做一个汉诺塔，
									//将n-1块移到B柱上，用hanoi函数解决。
		printf("%c->%c\n",a,c);		//n-1块移到B柱上后，将最底下的一块移到C上。
		hanoi(n-1,b,a,c);			//最后，将在B上的n-1块，通过hanoi的功能，移到C上。
	}
}
int main(void){
    
	hanoi(2,'A','B','C');

	getchar();						//便于看到输出结果。
	return 0;
}