导入库

#pragma comment(lib,"add.lib");

形式

• 间接递归：函数A调用函数B，函数B再调用函数A
• 直接递归：函数直接调用自身

递归

递归（recursion）指函数调用自身 通过少量程序描述出解题过程中需要的多次的重复计算，减少代码量 把大型复杂的问题转化为一个与原问题相似的较小规模的问题来求解

• 递归编程思路的实现

1. 明确递归函数所要实现的函数功能
2. 使用switch/if声明结束条件，寻找调用过程中参数n所代表的问题规模足够小的时候所return的定值
3. 寻找递归的等价表达式

int f(int n){
	swich(n){
		case 1://问题规模足够小
			return 1;
		dafault：
			return f(n-1)+f(n-2);//等价关系式
	}
}

• 编写递归程序时还需注意：

1. 注意表达式在递归过程中不可越界，防止递归函数体所提供的结束条件不足以退出本层递归导致递归函数的无限循环调用，引起死循环

• 递归优化

1. 当问题规模n足够大，且等价表达式并列调用递归函数时，相当一部分f(n)被重复计算

维护一个数组，保存f(n)中的所有计算结果，未计算过赋值-1，下面是优化样例

int f(int n){
    switch(n){
        case 1:
            return 1;
        case 2:
            return 1;
        default:
            if(arr[n] != -1){
                return arr[n];
            }else{
                arr[n] = f(n-1) + f(n-2);
                return arr[n];
            }
    }
}

2.问题规模n过大导致向下递归过多，栈空间不够，导致栈溢出

1. 此时可以考虑自底向上的递推，即通过普通的循环解决问题
2. 考虑将局部对象设置为static对象从而防止栈溢出

实例：汉诺塔问题

实现递归之前首先要设计递归函数，汉诺塔问题的解决方式为

1.将f(n-1)个积木从from移向buffer 2.将剩下的1个积木从from移向to 3.将f(n-1)个从buffer移向to

其实汉诺塔问题的大小规模转换就是一个5层的汉诺塔问题可以转换成两个四层的汉诺塔，以此类推，这才是本问题的实质。 这里的f(n)指的是将n个积木从一根柱子移向另一根柱子所用的次数