8.3 递归与循环电子课件 计算机系统基础：C语言视角（RISC-V版）.ppt

8.3 递归与循环电子课件 计算机系统基础：C语言视角（RISC-V版）递归与循环递归与循环递归与循环递归与循环在程序设计中，所有的递归函数都可以用传统的在程序设计中，所有的递归函数都可以用传统的循环（如循环（如forfor和和whilewhile循环）来实现循环）来实现某些程序设计问题，递归版本要比重复版本更简单某些程序设计问题，递归版本要比重复版本更简单哪些问题需要递归，哪些问题用循环哪些问题需要递归，哪些问题用循环?递归是很有用的，但是需要付出代价递归是很有用的，但是需要付出代价运行时间运行时间使用数值很大的使用数值很大的n n，对，对SnSn的循环结构版本与递的循环结构版本与递归版本进行对比归版本进行对比intLoopSn(intn)intresult=0;inti=1;for(i=1;i=n;i+)result=result+i;returnresult;int Sn(int n)int Sn(int n)int result;int result;if(n=1)if(n=1)return 1;return 1;else else result=Sn(n-1)+n;result=Sn(n-1)+n;return result;return result;对比对比使用库函数获得函数开始和结束时的时间使用库函数获得函数开始和结束时的时间例如，例如，gettimeofdaygettimeofday库函数库函数#include#includeintSn(intn);/采用递归实现的采用递归实现的SnintLoopSn(intn);/采用采用for循环实现的循环实现的Snintmain()intin;intsum;doubletimeuse;printf(Inputn:);scanf(%d,&in);structtimevaltv_begin,tv_end;gettimeofday(&tv_begin,NULL);sum=LoopSn(in);gettimeofday(&tv_end,NULL);timeuse=(tv_end.tv_sec-tv_begin.tv_sec)+(tv_end.tv_usec-tv_begin.tv_usec)/1000000.0;printf(time=%fn,timeuse);/打印出采用循环结构的打印出采用循环结构的Sn运行时间运行时间printf(%dn,sum);gettimeofday(&tv_begin,NULL);sum=Sn(in);gettimeofday(&tv_end,NULL);timeuse=(tv_end.tv_sec-tv_begin.tv_sec)+(tv_end.tv_usec-tv_begin.tv_usec)/1000000.0;printf(time=%fn,timeuse);/打印出采用递归结构的打印出采用递归结构的Sn运行时间运行时间printf(%dn,sum);实验分析实验分析对于不同的对于不同的n n的值，递归版本相对要慢（假设的值，递归版本相对要慢（假设编译器没有优化递归）编译器没有优化递归）原因：原因：采用递归函数，需要执行更多的指令采用递归函数，需要执行更多的指令每一次递归调用，都要执行参数传递、寄存器保存每一次递归调用，都要执行参数传递、寄存器保存/恢恢复等指令，影响了效率复等指令，影响了效率对于循环版本，只需要执行一次函数调用对于循环版本，只需要执行一次函数调用栈溢出栈溢出计算计算S Sn nRV32IRV32I计算机，支持的整数为计算机，支持的整数为3232位位不发生溢出的情况下，不发生溢出的情况下，n n的取值最大可以是的取值最大可以是2 21616-1-1，即，即6553565535调用调用SnSn的递归函数，可能达不到这个最大值的递归函数，可能达不到这个最大值如果递归调用次数过多，就可能导致占用的栈空如果递归调用次数过多，就可能导致占用的栈空间超过操作系统为其分配的最大值间超过操作系统为其分配的最大值导致导致栈溢出栈溢出，程序异常退出，计算不出结果，程序异常退出，计算不出结果假设仅有假设仅有100KB100KB连续的存储单元提供给连续的存储单元提供给SnSn函数做函数做运行时栈使用，运行时栈使用，SnSn函数的栈帧大小为函数的栈帧大小为1616个单元，个单元，n n的取值最大仅可以是的取值最大仅可以是64006400