一步一步写算法(之循环和递归).doc

一步一步写算法（之循环和递归） 【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：】 其实编程的朋友知道，不管学什么语言，循环和递归是两个必须学习的内容。当然，如果循环还好理解一点，那么递归却没有那么简单。我们曾经对递归讳莫如深，但是我想告诉大家的是，递归其实没有那么可怕。所谓的递归就是函数自己调用自己而已，循环本质上也是一种递归。 1）求和递归函数 我们可以举一个循环的例子，前面我们说过，如果编写一个1到n的求和函数怎么写呢，你可能会这么写：1. intcalculate(intm)2. 3. intcount=0;4. if(m0)5. return-1;6. 7. for(intindex=0;index=m;index+)8. count+=index;9. 10. returncount;11. int calculate(int m)int count = 0;if(m 0)return -1;for(int index = 0; index = m; index+)count += index;return count; 上面只是一个示范。下面我们看看如果是递归应该怎么写呢？ 1. intcalculate(intm)2. 3. if(m=0)4. return0;5. else6. returncalculate(m-1)+m;7. int calculate(int m)if(m = 0)return 0;elsereturn calculate(m -1) + m; 大家看着两段代码有什么不同？ （1）第一段代码从0，开始计算，从0到m逐步计算；第二段代码是从10开始计算，逐步到0之后这回，这样同样可以达到计算的效果 （2）第一段代码不需要重复的压栈操作，第二段需要重复的函数操作，当然这也是递归的本质 （3）第一段代码比较长，第二段代码较短 2）查找递归函数 大家可能说，这些代码有些特殊。如果是查找类的函数，有没有可能修改成递归函数呢？1. intfind(intarray,intlength,intvalue)2. 3. intindex=0;4. if(NULL=array|0=length)5. return-1;6. 7. for(;indexlength;index+)8. 9. if(value=arrayindex)10. returnindex;11. 12. 13. return-1;14. int find(int array, int length, int value)int index = 0;if(NULL = array | 0 = length)return -1;for(; index data);8. pNode=pNode-next;9. 10. void print(const NODE* pNode)if(NULL = pNode)return;while(pNode)printf(%dn, pNode-data);pNode = pNode-next; 那么此时如果改成递归，那就更简单了：1. voidprint(constNODE*pNode)2. 3. if(NULL=pNode)4. return;5. else6. printf(%dn,pNode-data);7. 8. print(pNode-next);9. void print(const NODE* pNode)if(NULL = pNode)return;else printf(%dn, pNode-data);print(pNode-next); 其实，写这么多，就是想和大家分享一下我个人的观点：循环是一种特殊的递归，只有递