栈的简单应用.ppt

栈的简单应用 五、栈与递归 栈的重要应用就是实现递归。 递归的定义： 一个直接或间接调用自己的函数。 例如：阶乘 函数调用之前 一个函数的在运行期间调用另一个函数， 在运行被调用函数之前，需先完成三项任务： 1、将实参、返回地址等信息传递给被调用函数保存，入栈； 2、为被调用函数的局部变量分配存储区； 3、将控制转移到被调用函数的入口。 函数调用之后 从被调用函数返回调用函数之前，应该完成 下列三项任务： 1、保存被调函数的计算结果； 2、释放被调函数的数据区； 3、依照被调函数保存的返回地址将控制转移到调用函数。 递归函数调用 递归函数执行的过程可视为同一函数进行嵌套调用的过程。 例如：汉诺塔游戏 void hanoi(int n,char x,char y,char z) { if (n==1) move(x,1,z); else{ hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); } } * * fact(n)= 1 n=1 n*fact(n-1) n1 4*fact(3) 4! a n= 4 a n=3 3! 3*fact(2) b c 2*fact(1) 2! n=2 n=1 b c 数据栈 地址栈 设n=4 x y z 源塔 目标塔 辅助塔 *