文档介绍：第3章递归算法递归算法概述递归是一种强有力的设计方法?递归算法的特点?简单明了易于证明?递归的效率问题递归算法的基本思想将求解某个较大的问题转化成若干个较小的问题,反复的进行转化直到问题小到可以直接求解,若这些较小的问题与较大的问题性质相同,则递归调用同样的算法进行求解。递归的条件(1)递归的下一步比上一步要简单;(2)在有限步内完成;(3)必须有递归出口。 A1:一次调用当主程序执行到Call A时,系统自动保存好1的地址,便于调用A结束后能从系统获得返回地址。主程序中有多次对同一程序A的调用。在第i次重复调用子程序A之前,系统自动的保存好地址i,便于第i次调用A结束后能顺利地按地址i返回。这种情况与1次调用不同,需要保存的地址有多个,但在某一时刻最多只有一个地址,一旦获得地址后后,保留地址被被释放。主程序子程序ACall A1:Call A2:n次调用主程序子程序A子程序BCall B2:Call A1:嵌套调用主程序子程序A子程序BCall B1:Call A2:平行调用对于上述两种情况当主程序执行到Call A或Call B时,系统自动地保存好地址1,在第二次调用子程序Call B或Call A时,再保存好地址2。这两种情况与前面两种情况不同,在某一时刻可能保存多个地址,而且后保存的地址先释放。这里的返回地址我们通常用栈这种数据结构来保存。栈在过程调用中的作用:在过程调用中我们需要将实参的值带给形参,需要将过程的返回地址临时存放在某处,在过程中还需要分配一些局部变量,这些数据通常我们将其存放在堆栈中。:一、按值传送(比如:C语言中的参数传递方式,以及在PASCAL中的值参)调用前后值参对应的实参不发生变化二、按地址传送(比如PASCAL中的变参)变参对应的实参的值将执行过程中对变参的修改进行回传。对于变参回传值,有两种实现方式:(1)两次值传方式。按指定类型为变参设置相应的存储空间,在执行调用时,将实参传送给变参,在返回时将变参的值回传给实参。(2)地址传送方式。在内部将变参设置一个地址,调用时首先执行地址传送,将实参的地址传送给变参,在子程序执行过程中,对变参的操作实际上变成对对应的实参的操作。在后面的讨论中,对变参的值的回传用第一种方式,即两次值传送方式。3. 子程序调用的内部操作(1)在执行调用时,系统执行的操作:a. 返回地址进栈,同时在栈顶为被调子程序的局部变量开辟空间;b. 为被调子程序准备数据:计算实参值,并赋给对应的栈顶的形参;c. 将指令流转入被调子程序的入口处。(2)在执行返回操作时,系统执行的操作:a. 若有变参或是函数,将其值保存到回传变量中;b. 从栈顶取出返回地址;c. 按返回地址返回;d. 若有变参或是函数,从回传变量中取出保存的值传送给相应的变量或位置上。Procedure main()Procedure A(x1,x2)…end AProcedure B(x3,x4)…call A(e,f)3:…end B…call A(a,b)1:…call B(c,d)2:…end main1a,b3e,fc,d2堆栈