数据结构与算法设计PPT (18).pdf

《数据结构与算法设计PPT (18).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (18).pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章递归5.1 递归程序设计递归程序设计采用问题分解的方式是一种解决问题的方法递归就是为这种程序设计方法提供支持的编程技术直接或者间接调用自身的函数过程称为递归函数递归函数直接或者间接调用自身的函数int s(int n)if(n=1)return 1;else return s(n-1)+n;怎样编写递归函数 递归函数的编写要十分小心 递归过程分解数据的规模，应使得递归越来越趋近比较容易解决的小问题规模 可以很容易得到问题答案的条件称之为基本条件 每个递归函数都必须要有一个基本条件（又称递归终结条件）可能会有多个递归的条件（又称递归条件）数学归纳法要证明数学归纳法证明的过程：（1）选取一个

2、比较小的n值证明这个等式成立（2）假设当n=k时等式成立证明当n=k+1时等式也是成立的数学归纳法数学归纳法基本条件 n=1 或者n=2数学归纳法假设 n=k时成立证明n=k+1成绩结论：对任意的n值都是成立的递归定义int s(int n)if(n=1)return 1;else return s(n-1)+n;递归函数要注意的问题：-什么是函数正常执行的参数范围-递归程序多次执行会带来数据溢出问题十进制数转任意进制问题递归定义递归问题定义：（1）n值比base小：直接输出（2）n值比base大：对n/base部分进行转换输出n%base部分十进制数转任意进制问题const char*DIG

3、IT_TABLE=0123456789abcdef;const int MAX_BASE=strlen(DIGIT_TABLE);void printIntRec(int n,int base)if(n=base)printIntRec(n/base,base);cout DIGIT_TABLE n%base;代码存在的问题:要转换进制大于16时会溢出;要转换进制为0时会产生被零除;要转换进制为1时会无限循环.递归函数的基本结构分支结构if (很容易解决的规模)/递归终结条件直接求解答案;else/递归条件分解数据规模，调用递归函数求解;递归深度过大会使得程序以Stack Overflow错误终止！递归程序常见错误