计算机程序设计基础课程教学PPTFOP.pptx

乔林计算机程序设计基础Email:Tel:华大学计算机科学与技术系

第十二章递归程序设计学习目标了解递归可以简化复杂问题的编程实现理解递归程序设计范型理解函数递归调用的内部实现机制熟悉典型递归程序的范例能够编写简单的递归程序

12.1递归问题的引入01简化复杂问题的手段：将问题逐步化简，在化简过程中保持原问题的性质不变，直到问题最简，可以轻易获得答案，然后将简化问题的答案组装成原始问题的解递归的目的02n!=1?2?3?…?n:n!=(n-1)!?n;0!=1xn=x?x?x?…?x:xn=xn-1?x;x0=1递归示例

longintCalFactorial(intn){longintresult=1;inti=0;while(++i=n)result*=i;returnresult;}递归函数示例一阶乘的计算longintCalFactorial(intn){longintresult;if(n==0||n==1)result=1;elseresult=n*CalFactorial(n–1);returnresult;}

递归函数示例二0102幂的计算longdoubleCalPower(longdoublex,intn){longdoubleresult;if(n==0)result=1;elseresult=x*CalPower(x,n–1);returnresult;}

递归函数示例三01求整数的各位数字之和单击此处添加小标题02intSumDigit(intn){if(n10)returnn;elsereturnn%10+SumDigit(n/10);}单击此处添加小标题

递归过程的跟踪阶乘的计算#includestdio.hlongintCalFactorial(intn){longintresult;if(n==0||n=1)result=1;elseresult=n*CalFactorial(n–1);returnresult;}voidmain(){intnum=3;longintfac;fac=CalFactorial(num);printf(“%ld”,fac);}

递归过程的跟踪main()函数栈框架

递归过程的跟踪第一次调用CalFactorial()函数栈框架longintCalFactorial(intn){longintresult;if(n==0||n=1)result=1;elseresult=n*CalFactorial(n–1);returnresult;}

递归过程的跟踪第二次调用CalFactorial()函数栈框架longintCalFactorial(intn){longintresult;if(n==0||n=1)result=1;elseresult=n*CalFactorial(n–1);returnresult;}

递归过程的跟踪第三次调用CalFactorial()执行后栈框架longintCalFactorial(intn){longintresult;if(n==0||n=1)result=1;elseresult=n*CalFactorial(n–1);returnresult;}

递归过程的跟踪第二次调用CalFactorial()执行后栈框架longintCalFactorial(intn){longintresult;if(n==0||n=1)result=1;elseresult=n*CalFactorial(n–1);returnresult;}

递归过程的跟踪第一次调用CalFactorial()执行后栈框架longintCalFactorial(intn){longintresult;if(n==0||n=1)result=1;elseresult=n*CalFactorial(n–1);returnresult;}

递归过程