栈的应用递归到非递归的转换张 铭 北京大学信息学院1内容提要递归函数调用原理 机械的递归转换 优化后的非递归函数 非递归的二叉树周游2张铭 北京大学信息学院递归函数示例void exmp(int n, int& f) { int u1, u2; if (n<2) f = n+1; else { exmp((int)(n/2), u1); exmp((int)(n/4), u2); f = u1*u2; } } 张铭3北京大学信息学院数学公式fu (n) ={n +1当n < 2时fu ( ⎣n / 2 ⎦)* fu ( ⎣n / 4 ⎦)n ≥ 2时}4张铭 北京大学信息学院函数调用及返回的步骤调用– 保存调用信息（参数，返回地址） – 分配数据区（局部变量） – 控制转移给被调函数的入口返回– 保存返回信息 – 释放数据区 – 控制转移到上级函数（主调用函数）5张铭 北京大学信息学院函数执行过程图解二叉树图解 Exmp(7,&f) f=u1*u2=4u1=f=2 u2=f=2 Exmp(3,&f) Exmp(1,&f) f=u1*u2=2u1=f=2 Exmp(1,&f)张铭u2=f=1 Exmp(0,&f)6北京大学信息学院用栈模拟递归调用过程后调用，先返回(LIFO），所以用栈rd=1: n=1 f=1 u1=? u2=? f=2 rd=2: n=0 f=? u1=? u2=? f=? rd=2: n=1 f=? u1=2 u2=1 rd=1: n=3 f=? u1=? u2=? f=2 u1=? u2=? rd=3: n=7 f=? u1=? u2=? u1=2 u2=2张铭7北京大学信息学院递归过程的模拟假设 void recfunc(p1, p2, p3，…，pk, pk+1, …, pm) 是一个递归函数void是无返回值型的函数，如果有返回值， 我们可以把返回值转换为一个引用型参数 其中参数p1, p2, p3，…，pk是值传递，参 数pk+1, …, pm是引用传递。
