递归的基础

　　递归的概念

　　•在程序中函数直接或间接调用自己•直接调用自己

　　•间接调用自己

　　•跳出结构,有了跳出才有结果

　　递归的思想

　　•递归的调用,最终还是要转换为自己这个函数•如果有个函数foo,如果他是递归函数,到最后问题还是转换为函数foo的形式

　　•递归的思想就是将一个未知问题转换为一个已解决的问题来实现

　　functionfoo(){

　　...foo(...)...

　　}

　　递归的步骤(技巧)

　　1.假设递归函数已经写好

　　2.寻找递推关系

　　3.将递推关系的结构转换为递归体

　　4.将临界条件加入到递归体中

　　简单递归练习

　　求1-100的和

　　•分析:

　　•假设递归函数已经写好为sum,既sum(100),就是求1-100的和

　　•寻找递推关系:就是n与n-1,或n-2之间的关系

　　sum(n)==sum(n-1)+n

　　varres=sum(100);

　　varres=sum(99)+100;

　　3.将递归结构转换成递归体

　　functionsum(n){

　　returnsum(n-1)+n;

　　}

　　4.将临界条件加入到递归中

　　•求100转换为求99

　　•求99转换为求98

　　•求98转换为求97

　　•...

　　•求2转换为求1

　　•求1转换为求1

　　•即sum(1)=1

　　5.递归函数

　　functionsum(n){

　　if(n==1)return1;

　　returnsum(n-1)+n;

　　求1,3,5,7,9,...第n项的结果和前n项和,序号从0开始

　　•分析•假设递归函数已经完成foo(n),得到奇数

　　•递归关系:◦foo(n)=foo(n-1)+2

　　•递归体

　　functionfoo(n){

　　returnfoo(n)=sum(n-1)+2;

　　}

　　4.跳出条件

　　•foo(n)=foo(n-1)+2

　　•foo(1)=foo(0)+2

　　•foo(0)=1;