3-4 栈与递归

递归的定义：

1. 若一个对象部分地包含它自己，或用自己给它自己定义，则这个对象是递归的（例：链表中结点的指针域）

2. 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程

   例：递归求n的阶乘

   long Fact(long n) {
   	if(n == 0) 
   		return 1;
   	else
   		return n*Fact(n-1);
   }
   

递归问题—用分治法求解：

分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解

必备的三个条件：

1. 能将一个问题转变为一个新问题，而新问题与原问题的解法相同或类似。不同的仅是处理的对象，且这些对象是有变化规律的
2. 可以通过上述转化而使问题简化
3. 明确有一个递归出口，或称递归的边界

分治法求解递归问题算法的一般形式：

void p(参数表) {
	if(递归结束参条件) 可直接求解步骤; ----基本项
	else p(较小的参数); ----递归项
}

函数调用过程：

调用前，系统完成：

1. 将实参、返回地址等传递给被调用函数
2. 为被调用函数的局部变量分配存储区
3. 将控制转移到被调用函数的入口