递归是计算机科学的一个重要概念是程序设计中的一种有效的方法在程序设计语言中被广泛应用。它是指函数、过程、子程序在运行过程中直接或间接调用自身而产生的重入现象。采用递归编写程序能使程序变得简洁清晰使人容易理解。递归算法描述简洁结构清晰算法的正确性比较容易证明。但是递归算法的执行效率低空间消耗多有时还会受到一些软、硬件环境条件的限制不能使用递归技术因此在某些时候还需要将递归算法转换为非递归算法。1. 递归的概念在调用一个函数的过程中又出现直接或间接地调用该函数本身称为函数的递归调用。C语言的特点之一就在于允许函数的递归调用。写一个最简单的C语言递归代码#includestdio.h// function recursionintmain(){printf(hello world\n);main();return0;}上述就是一个简单的的递归程序只不过上面的递归是为了演示递归的基本形式不是为了解决问题代码最终会陷入死递归导致栈溢出。2. 具有递归特性的问题递归算法就是在算法中直接或间接调用算法本身的算法。使用递归算法有以下两个两个前提① 原问题可以层层分解为类似的子问题且子问题比原问题的规模更小。② 规模最小的子问题具有直接解。设计递归算法的原则是用自身的简单情况来定义自身。设计递归算法的方法如下。① 寻找分解方法将原问题转化为子问题求解。② 设计递归出口根据规模最小的子问题确定递归终止条件。3. 递归的限制条件① 递归存在限制条件当满足这个限制条件的时候递归便不再继续。② 每次递归调用之后越来越接近这个限制条件。4. 递归过程的实现递归进层时系统需要做三件事① 保留本层参数与返回地址。② 为被调用函数的局部变量分配存储区给下层参数赋值。③ 将程序转移到被调用函数的入口。而从被调用函数返回调用函数之前递归退层时系统也相应完成三件事① 保存被调用函数的计算结果。② 释放被调用函数的数据区恢复上层参数。③ 依照被调用函数保存的返回地址将控制转移回调用函数。当递归函数调用时应按照“后调用先返回”的原则处理调用过程。系统将整个程序运行时所需的数据空间安排在一个栈中每当调用一个函数时就为它在栈顶分配一个存储区而每当从一个函数推出时就释放它的存储区。一个递归函数的运行中调用函数和被调用函数是同一个函数因此与每次调用相关的一个重要概念就是递归函数运行的“层次”。假设调用该递归函数的主函数为第 0 层则从主函数调用递归函数为进入第 1 层…从第 i 层递归调用该函数为进入其“下一层”即第 i1 层反之退出第 i 层递归应返回至其“上一层”即第 i-1 层。为了保证递归函数正确执行系统需要设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个工作记录其中包含所有实在参数、所有局部变量以及上一层返回地址。每进入一层递归就产生一个新的工作记录压入栈顶每退出一层递归就从栈顶弹出一个工作记录。因此当前执行层的工作记录必为递归工作栈栈顶的工作记录该记录称为活动记录指示活动记录的栈顶指针成为当前环境指针。由于递归工作栈是由系统来管理的无须用户操心所以用递归法编制程序非常方便。5. 递归算法到非递归算法的转换递归算法具有以下两个特性① 递归算法是一种分而治之、把复杂问题分解为简单问题的问题求解方法对求解某些复杂问题递归分析方法是有效的。② 递归算法的效率较低。为此在求解某些问题时希望用递归算法分析问题用非递归算法求解具体问题。消除递归的原因① 有利于提高算法的时空性能因为递归执行时需要系统提供隐式栈来实现递归所以效率较低。② 无应用递归语句的语言设施环境条件下有些计算机语言不支持递归功能如 FORTRAN。③ 递归算法是一次执行完成的中间过程对用户不可见这在处理有些问题时不适用。基于以上原因需要把一个递归算法转换为非递归算法。理解递归机制是掌握递归程序设计的必要前提。消除递归应基于对问题的分析常用的有以下两类消除递归的方法① 简单递归问题的转换对于尾递归和单向递归的算法可用循环结构的算法代替。② 基于栈的方式即递归中隐含的栈机制转换为由用户直接控制的明显的栈利用栈来保存参数由于栈的后进先出特性吻合算法的执行过程因而可以用非递归算法代替递归算法。简单递归的消除在简单情况下可以将递归算法转换为线性操作序列直接用循环实现。① 单向递归单向递归是指递归函数中虽然有多次递归调用语句但各次递归调用语句的参数只和主调用函数有关相互参数之间无关并且这些递归调用语句处于算法的最后。② 尾递归尾递归是指递归调用语句只有一个而且是处于算法的最后。尾递归是单向递归的特例。6. 递归举例6.1 求n的阶乘6.2 顺序打印一个整数的每一位#includestdio.hvoidPrint(intx){if(x9){Print(x/10);}printf(%d ,x%10);}intmain(){intn0;scanf(%d,n);Print(n);return0;}6.3 求第n个斐波那契数#define_CRT_SECURE_NO_WARNINGS#includestdio.h#includetime.hintfib(intx){if(x2){return1;}else{returnfib(x-1)fib(x-2);}}intmain(){clock_tstart,end;startclock();intn0;scanf(%d,n);printf(%d\n,fib(n));endclock();printf(%.6f\n,(double)((end-start)/CLOCKS_PER_SEC));return0;}#define_CRT_SECURE_NO_WARNINGS#includestdio.h#includetime.hintmain(){clock_tstart,end;startclock();inta1;intb1;intc1;intn0;scanf(%d,n);inti0;while(n2){cab;ab;bc;n--;}endclock();printf(%d\n,c);printf(%.6f\n,(double)((end-start)/CLOCKS_PER_SEC));return0;}
