文档介绍：1 计算机程序设计基础第十二章递归程序设计??学****目标学****目标––了解递归可以简化复杂问题的编程实现了解递归可以简化复杂问题的编程实现––理解递归程序设计范型理解递归程序设计范型––理解函数递归调用的内部实现机制理解函数递归调用的内部实现机制––熟悉典型递归程序的范例熟悉典型递归程序的范例––能够编写简单的递归程序能够编写简单的递归程序 2 计算机程序设计基础 递归问题的引入??递归的目的递归的目的––简化复杂问题的手段:将问题逐步化简,在化简简化复杂问题的手段:将问题逐步化简,在化简过程中保持原问题的性质不变,直到问题最简, 过程中保持原问题的性质不变,直到问题最简, 可以轻易获得答案,然后将简化问题的答案组装可以轻易获得答案,然后将简化问题的答案组装成原始问题的解成原始问题的解??递归示例递归示例––n n ! = 1 ! = 1 ?? 2 2 ?? 3 3 ??……??n n: : n n ! = ( ! = ( n n?? 1)! 1)! ??n n ; 0! = 1 ; 0! = 1 ––x x n n = = x x ??x x ??x x ??……??x x: : x x n n = = x x n n??1 1??x x; ; x x 0 0 = 1 = 1 3 计算机程序设计基础递归函数示例一??阶乘的计算阶乘的计算 long int long int CalFactorial CalFactorial ( int ( int n n ){ ){ long int long int result result = 1; = 1; int int i i = 0; = 0; while( ++ while( ++ i i <= <= n n ) ) result result * *= = i i; ; return return result result ; ;} } long int long int CalFactorial CalFactorial ( int ( int n n ){ ){ long int long int result result ; ; if( if( n n == 0 || == 0 || n n = 1 ) = 1 ) result result = 1; = 1; else else result result = = n n* * CalFactorial CalFactorial ( ( n n–– 1 ); 1 ); return return result result ; ;} } 4 计算机程序设计基础递归函数示例二??幂的计算幂的计算 long double long double CalPower CalPower ( long double ( long double x x , int , int n n ) ) { { long double long double result result ; ; if( if( n n == 0 ) == 0 ) result result = 1; = 1; else else result result = = x x* * CalPower CalPower ( ( x x, , n n–– 1 ); 1 ); return return result result ; ;} } 5 计算机程序设计基础递归函数示例三??求整数的各位数字之和求整数的各位数字之和 int int SumDigit SumDigit ( int ( int n n ) ) { { if( if( n n < 10 ) < 10 ) return return n n; ; else else return return n n % 10 + % 10 + SumDigit SumDigit ( ( n n / 10 ); / 10 ); } } 6 计算机程序设计基础递归过程的跟踪??阶乘的计算阶乘的计算#include <> #include <> long int long int CalFactorial CalFactorial ( int ( int n n ){ ){ lo