会计学5.1递归与递归程序设计在一个函数的定义中出现了对自己(zìjǐ)本身的调用，称之为直接递归；或者一个函数p的定义中包含了对函数q的调用，而q的实现过程又调用了p，即函数调用形成了一个环状调用链,这种方式称之为间接递归。递归技术在算法和程序设计中是一种十分有用的技术，许多高级程序设计语言均提供了支持递归定义的机制和手段。例1试编一个递归函数，求正整数n的阶乘值n！。用fact(n)表示n的阶乘值，据阶乘的数学定义可知：1n=0fact(n)=n*fact(n-1)n>0该问题的算法(suànfǎ)为：intFact(intn){intm;if(n==0)return(1);else{m=n*Fact(n-1);return(m);}}例2试编一个递归函数，求第n项Fibonacci级数的值。假设使用Fibona(n)表示第n项Fibonacci级数的值，根据Fibonacci级数的计算公式：1n=1Fibona(n)=1n=2Fibona(n-1)+Fibona(n-2)n>2该问题(wèntí)的算法为：intFibona(intn){intm;if(n==1)return(1);elseif(n==2)return(1);else{m=Fibona(n-1)+Fibona(n-2);return(m);}}递归程序设计具有以下两个特点：（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到(dédào)满足时，递归执行过程便终止。有些问题的递归程序可能存在几个递归出口；（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，这些子问题的结构与原问题的结构相同，但规模较原问题小。子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。5．2递归程序执行过程的分析在递归程序的运行过程中，系统内部设立了一个栈，用于存放每次函数调用与返回所需的各种数据，主要包括：函数调用执行完成时的返回地址、函数的返回值、每次函数调用的实在参数和局部变量。在递归程序的执行过程中，每当执行函数调用时，必须完成以下任务：（1）计算当前被调用函数每个实在参数的值；（2）为当前被调用的函数分配一片存储空间，用于存放其所需的各种数据，并将这片存储空间的首地址压入栈中；（3）将当前被调用函数的实在参数、将来当前函数执行完毕后的返回地址等数据存入上述(shàngshù)所分配的存储空间中；（4）控制转到被调用函数的函数体，从其第一个可执行的语句开始执行。当从被调用的函数(hánshù)返回时，必须完成以下任务：（1）如果被调用的函数(hánshù)有返回值，则记下该返回值，同时通过栈顶元素到该被调用函数(hánshù)对应的存储空间中取出其返回地址；（2）把分配给被调用函数(hánshù)的那片存储空间回收，栈顶元素出栈；（3）按照被调用函数(hánshù)的返回地址返回到调用点，若有返回值，还必须将返回值传递给调用者，并继续程序的执行。例3试编写一个递归函数，在第一行打印输出1个1，在第二行打印输出2个2，……在第n行打印输出n个n。例如，当n=5时，调用该函数的输出结果(jiēguǒ)为：122333444455555该问题的算法为:print(intn){inti;if(n!=0){print(n-1);for(i=1;i<=n;i++)printf("%d",n);printf("\n");}}Print(5)Fibona(5)5.3递归程序到非递归程序的转换采用递归方式实现问题(wèntí)的算法程序具有结构清晰、可读性好、易于理解等优点，但递归程序较之非递归程序无论是空间需求还是时间需求都更高，因此在希望节省存储空间和追求执行效率的情况下，人们更希望使用非递归方式实现问题(wèntí)的算法程序；另外，有些高级程序设计语言没有提供递归的机制和手段，对于某些具有递归性质的问题(wèntí)（简称递归问题(wèntí)）无法使用递归方式加以解决，必须使用非递归方式实现。因此，本小节主要研究递归程序到非递归程序的转换方法。一般而言，求解递归问题有两种方式(fāngshì)：（1）在求解过程中直接求值，无需回溯。称这类递归问题为简单递归问题；（2）另一类递归问题在求解过程中不能直接求值，必须进行试探和回溯，称这类递归问题为复杂递归问题。两类递归问题在转换成非递归方式(fāngshì)实现时所采用的方法是不同的。通常简单递归问题可以采用递推方法直接求解；而复杂递归问题由于要进行回溯，在实现过程中必须借助栈来管理和记忆回溯点。5.3.1简单递归程序到非递归程序的转换采用递归技术求解问题的算法程序是自顶向下产生(chǎns