void main() { long int CalFactorial ( int n ) int num { num = 3; long int fac; long int result = 1; n fac = CalFactorial ( num ); int i = 0; fac printf ( "%ld", fac ); while( ++i <= n ) result *= i; result } return result ;
long double CalPower( long double x, int n ) { long double result; if( n == 0 ) result = 1; else result = x * CalPower( x, n – 1 ); return result; }
递归函数示例三
Email: qiaolin@ Tel: 62780973
清华大学计算机科学与技术系 乔 林
计算机程序设计基础
第十二章 递归程序设计
• 学习目标
– 了解递归可以简化复杂问题的编程实现
– 理解递归程序设计范型 – 理解函数递归调用的内部实现机制 – 熟悉典型递归程序的范例 – 能够编写简单的递归程序
long int CalFactorial( int n ){ long int result; if( n == 0 || n = 1 ) result = 1; else result = n * CalFactorial( n – 1 ); return result; }
பைடு நூலகம்
递归过程的跟踪
• main() 函数栈框架
void main() { int num = 3; long int fac; fac = CalFactorial ( num ); printf ( "%ld", fac ); }
num fac
3
递归过程的跟踪
• 第一次调用 CalFactorial() 函数栈框架
• 第二次调用 CalFactorial() 函数栈框架
void main() long int CalFactorial ( int n ) { long int CalFactorial ( int n ) long int result = 1; n { int i = 0; long int result = 1; n while( ++ i <= n ) result *= i ; int i = 0; result return result ; while( ++ i <= n ) result *= i; result } return result ;
long int CalFactorial( int n ){ long int result; if( n == 0 || n == 1 ) result = 1; else result = n * CalFactorial( n – 1 ); return result; }
递归函数示例二
• 幂的计算
3
2
}
long int CalFactorial( int n ){ long int result; if( n == 0 || n = 1 ) result = 1; else result = n * CalFactorial( n – 1 ); return result; }
递归过程的跟踪
• 求整数的各位数字之和
int SumDigit( int n ) { if( n < 10 ) return n; else return n % 10 + SumDigit( n / 10 ); }
递归过程的跟踪
• 阶乘的计算
#include <stdio.h> long int CalFactorial( int n ){ long int result; if( n == 0 || n = 1 ) result = 1; else result = n * CalFactorial( n – 1 ); return result; } void main(){ int num = 3; long int fac; fac = CalFactorial( num ); printf( “%ld”, fac ); }
}
3
3
long int CalFactorial( int n ){ long int result; if( n == 0 || n = 1 ) result = 1; else result = n * CalFactorial( n – 1 ); return result; }
递归过程的跟踪
12.1 递归问题的引入
• 递归的目的
– 简化复杂问题的手段：将问题逐步化简，在化简 过程中保持原问题的性质不变，直到问题最简， 可以轻易获得答案，然后将简化问题的答案组装 成原始问题的解
• 递归示例
– n! = 1 2 3 … n: n! = (n-1)! n; 0! = 1
• 第三次调用 CalFactorial() 执行后栈框架
void main()
long int CalFactorial ( int n ) long int CalFactorial ( int n ) { long int CalFactorial ( int n ) long int result = 1; n { int i = 0; long int result = 1; n while( ++ i <= n ) result *= i ; int i = 0; result return result ; while( ++ i <= n ) result *= i; result } return result ;
– x = x x x … x: x = x
n n n- 1
x; x = 1
0
递归函数示例一
• 阶乘的计算
long int CalFactorial( int n ){ long int result = 1; int i = 0; while( ++i <= n ) result *= i; return result; }