考虑函数的递归,因为第N次与第N+1次调用所采用的栈不能重用,可能会导致多次调用后,进程分配的栈空间耗尽.
解决的方法之一就是用自己可控制的栈代替函数调用栈,从而实现递归到非递归的转换.(用户栈当然必须是可以重用的,否则也就没有意义).
我们将会发现,实际上用户栈相比函数调用栈来说,可以非常小下面就以ackerman函数为例
二.ackerman函数
已知Ackerman函数akm(m,n)定义如下：
当m=0时:
akm(m,n) = n + 1;
当m!=0, n=0时: akm(m,n) =
akm(m-1, 1);
当m!=0, n!=0时: akm(m,n) = akm(m-1, akm(m,
n-1));
(1) 根据定义，写出它的递归求解算法；
(2) 利用栈，写出它的非递归求解算法。
【解答】
(1) 已知函数本身是递归定义的，所以可以用递归算法来解决：
unsigned akm ( unsigned m, unsigned n ) {
if ( m == 0 ) return
n+1; //
m == 0
else if ( n == 0 ) return akm ( m-1, 1
); //
m > 0, n == 0
else return akm ( m-1, akm ( m, n-1 ) );
// m > 0,
n > 0
}
(2) 为了将递归算法改成非递归算法.
首先改写原来的递归算法，将递归语句从结构中独立出来：
unsigned akm ( unsigned m, unsigned n ) {
unsigned v;
if ( m == 0
) return
n+1; //
m == 0
if ( n == 0
) return akm ( m-1, 1
);
// m > 0, n ==0
v = akm ( m,
n-1 ) );
//
m > 0, n > 0
return akm ( m-1, v );
}
然后,就是递归转非递归的标准流程:
a. 从一个简单的实例,分析其递归调用树
b. 分析哪些元素需要放在栈中
c. 跟踪递归调用过程,分析栈的变化
d. 由实例->普遍,演绎出算法,这一过程也称作建模
我们将会发现,建模是最困难的.
下面,我们就以ack(2,1)为例,开始分析递归调用树,采用一个栈记忆每次递归调用时的实参值，每个结点两个域{vm,
vn}。对以上实例，递归树以及栈的变化如下：
相应算法如下
#include
#include
using namespace std;
typedef struct node_t {
unsigned int vm, vn;
}node, *pnode;
unsigned akm ( unsigned int m, unsigned int n
) {
std::stack st;
pnode w, w1;
unsigned int v;
unsigned int vt;
//根节点进栈
w = (node *) malloc (sizeof (node));
w->vm = m;
w->vn = n;
st.push (w);
do {
//计算akm(m-1, akm(m,
n-1))
while ( st.top( )->vm > 0
)
{
vt
= w->vn;
//计算akm(m,
n-1), 直到akm(m,0)
while ( st.top()->vn > 0 )
{
w1 = (node *) malloc (sizeof (node));
vt --;
w1->vn = vt;
w1->vm = w->vm;
st.push( w1 );
}
//把akm(m,
0)转换为akm(m-1, 1),并计算
w = st.top( );
st.pop(
);
w->vm--;
w->vn = 1;
st.push( w );
vt = w->vn;
}
//计算akm(
0, akm( 1, * )
)
w =
st.top();
st.pop(
);
w->vn++;
//计算v = akm( 1, * )+1
v = w->vn;
//如果栈不为空,改栈顶为(
m-1, v )
if (
!st.empty( )
)
{
w = st.top();
st.pop( );
w->vm--;
w->vn = v;
st.push( w );
}
} while ( !st.empty( ) );
return v;
}
int main()
{
unsigned int rtn;
rtn = akm(3,2);
std::cout << rtn << std::endl;
return 0;
}
三.小结
主要难点在于最后的建模,怎样从一个或者几个实例,演绎出普适的数学模型,这是我做不到的,只有试图去理解,我想,勤能补拙只不过是一种安慰,真正创造性的工作,的确是聪明人的专利.另外一点感触就是,栈的应用可真是灵活啊!
