未用--递与归程序执行过程 .pptVIP

* 8.4.4　递归程序执行过程 递归程序写起来简单、风格也优美。但是，执行时能得到正确的结果吗？回答是肯定的，这是由 C 系统保证的。 C系统在执行函数调用时，按右图所示步骤进行（凡是允许递归的程序设计语言在执行函数调用时，都按这个步骤进行）。 其中，关键是“开辟新的运行环境”和“释放本函数的运行环境”两步。所谓运行环境，就是本函数运行时所需要的存储空间(形式参数单元、局部变量单元、临时变量单元等)、以及为了保存（调用本函数之前）程序运行的现场所需要的空间等。 开辟新的运行环境 保存现场 参数结合 执行 分程序 恢复现场 释放本函数的运行环境 返回 为了简洁，目前我们仅涉及： 本函数值单元 返回地址单元 本函数的形式参数单元区 本函数的局部变量单元区 本函数的临时变量单元区 由于每次调用函数时，都在新的运行环境下运行，保证了存储单元不发生冲突，从而也就保证了递归程序执行的正确性。为了加深对递归程序的理解，我们再举一个递归程序的例题，并观察它的执行过程。 【例7-11】从前 n 个自然数 1 , 2 , 3 , ... , n 中取 r 个数作组合，打印全部所有组合。例如，n=5 、r=3 ，便有如下10种组合。 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 解本题的一般想法是使用 r 重循环 for ( i1 = 1 ; i1 =n-r+1 ; i1 ++ ) for ( i2 = i1+1 ; i2 = n-r+2 ; i2 ++ ) ... ... for ( ir = ir-1+1 ; ir = n ; ir ++ ) 印( i1 , ... , ir ) 但是，由于 r 是可变的，所以循环嵌套层数亦是可变的，因此不知道应该用多少个 i 。我们只好从另一角度上想问题，自然想到递归。 从前 n 个自然数 1 , 2 , 3 , ... , n 中取 r 个数作组合的问题可以分解成： 先分别取这 n 个数中的一个数i（只需要在前 n-r+1 个数中取 i ）； 然后从该 i 后边的 n-i+1 个数 i+1 , i+2 , ... , n 中取 r-1 个数作组合； 最后把每组 r-1 个数的组合与前边的 i 合并，从而构成 r 个数的组合。 当然，从 i 后取 r-1 个数作组合的问题还可以用同样的方法来分解。 我们设想，若有一个函数 combination ( s , j ) 能够完成从自然数子序列 s , s+1 , s+2 , ... , n 中取 j 个数作组合，则我们的原始问题可以写成函数调用： combination ( 1 , r ) 而我们的第一步分析算法则可以写成： for i = 1 TO n-r+1 DO combination ( i+1 , r-1 ) 把该算法抽象化，并考虑递归出口（当j=1时，就不必再继续递归下去，只需打印已经形成的组合），得到函数： void combination ( int s, int j ) { int i ; for ( i=s ; i=n-j+1 ; i++ ) if ( j1 ) combinatien( i+1 , j-1 ) else 打印每层递归进入本函数时的 i } 主程序中说明变量 n 、r ；输入 n 、r 后，以语句combination(1,r)调用该函数，就是我们的分析算法，也就得到前边的r重循环程序。 该程序无法在第 r 层递归调用时，访问（打印）前边诸层调用时的局部量i 。显然每层的i必须： 或者在本层调用时打印; 或者用一个全局数组变量，