试将下列递归过程改写为非递归过程。

试编写如下定义的递归函数的递归算法，并根据算法画出求g(5，2)时栈的变化过程。

若假定机器字长无限，移位操作只需单位时间，递归不会溢出，且rand()为理想的随机数发生器。试分析以下函数F(n)，并以大o记号的形式确定其渐进复杂度的紧上界。

文法GIE]是LL(1)文法：

其中E，F，E'，F'为非终结符。

对文法G[E]构造递归下降分析程序。

关于kd-树查找算法kdSearch()(教244页算法8.2)，试证明以下结论：

a)在树中某一节点发生递归，当且仅当与该节点对应的子区域，与查询区域的边界相交;

b)若令Q(n)=规模为n的子树中与查询区域边界相交的子区域(节点)总数，则有：Q(n)=2+2Q(n/4)=o(√n)。

c)kdSearch()的运行时间为：o(r+√n)，其中r为实际命中并被报告的点数。

d)进一步地，试举例说明，单次查询中的确可能有多达Ω(√n)个节点发生递归，故以上估计是紧的。

e)若矩形区域不保证与坐标轴平行，甚至不是矩形(比如圆)，则上述结论是否依然成立？

设f是三元原始递归全函数,g定义为

(1)若h(x)=,(8(x,y))=0),则此时称h为 递归函数是否妥当？为什么？

(2)证明下列函数h是μ-递归函数:

Ackermann函数A(m,n)可递归定义如下:

试设计一个计算A(m,n)的动态规划算法,该算法只占用O(m)空间(提示:用两个数组val[0:m]和ind[0:m],使得对任何i有val[i]=A(i,ind[i])).