5-1 已知A[n]为整数数组，试写出实现下列运算的递归算法：
(1)求数组A中的最大整数。
(2)求n个整数的和。
(3)求n个整数的平均值。

解：
(1)思路：求A(n)中的最大整数，等价于比较A[n-1]与A(n-1)中的最大值，谁大就返回谁.A(n-1)看起来有点别扭，其实是指前n-1个数，从A[0]~A[n-2]。
于是我们可以这样设计函数

int max(int n){
  if(n == 1)            //递归结束条件
    return A[0];  
  else{
    int tmp=max(n-1);   //返回A(n-1)的最大值
    return A[n-1]>=tmp?A[n-1]:tmp;
}

(2)思路：和上题一样

int sum(int n){
   if(n == 1)
     return A[0];
   else return A[n-1]+sum(n-1);
}

(3) 用递归求平均值有意义么？

5-2 已知Ackerman函数定义如下:

              |n+1                  当m=0时.
    akm(m,n)= |akm(m-1,1)           当m!=0,n=0时.
              |akm(m-1,akm(m,n-1))  当m!=0,n!=0时

(1)根据定义，写出它的递归求解算法；
(2)利用栈，写出它的非递归求解算法.

(1)依样画葫芦，相当于直接把函数抄下来

int akm(int m,int n){
  if(m != 0)
    if(n != 0)
      return akm(m-1,akm(m,n-1));
    else return akm(m-1,1);
  else reurn n+1;
}

(2)看了好久的答案才明白这类题的做法，我的理解如下：
a. 作为一个递归函数什么时候需要栈呢？
如果akm(m,n)能够等价于另一个简单的akm(x,y)，那么这时候就不需要工作栈，直接变换就行。比如“斐波那契数列”；只有形如akm(..akm(..akm(..)...)这个时候需要栈，因为m，n的变换必须依靠下一步的结果，也就是说你除了把这一步先保存起来，别无他法，你永远不知道它下一步会变成什么。没有一个简单的变化，这时候就需要工作栈.
b. 哪些变量需要进栈？以及如何判断进栈和出栈
那些与其他参数的下一步结果相关的变量需要进栈。这里便是akm函数的第一个参数m。
在我们得到下一组n的值之前，m必须先被保存起来，我们没有办法先运算m。而n的值恰好是尾递归.

进栈与出栈的条件一般已经在函数或者题意中给出，比如这个函数可以直接按照函数结构来写。

int akm(int m,int n){
   int vn=n,vm;
   stack st;    //就不写最大元素数了.
   st.Push(m);       //栈，保存一系列参数m
   while(!st.IsEmpty()){
     vm=st.Pop();
     if(vm == 0)vn++;      //函数的第一个分支条件
       else if(vn == 0){   //第二分支条件
         st.Push(vm-1);vn=1;
       }
          else{            //第三个分支条件
            st.Push(vm-1);  
            st.Push(vm);
            vn--;
          }   
   }
   return vn;
}

这道题做了我足足两天之久。第一次接触 递归和循环 结构的转换，非常努力的试图搞懂它，最后刹那间明了，欣喜若狂，忍不住糊诌几句。
花了很多时间才看懂参考答案的意思，它是通过找出栈的变换规律，然后具体问题具体分析，总结出来，再写成循环结构。不过这样的规律并不一定好找，我一开始之所以看不懂的原因也在于此，因为我总觉得它应该从普遍性入手。
后来我就一直思考，栈为什么要存在，必要性在哪里，是什么原因导致了函数的无规律变换，而需要一串的地址去存储它的自变量或者中间量。哪些元素又是必须依靠栈去保留呢。
当我凝视着窗外烈日底下在风中轻轻舞动的树叶，交织出婆娑的树影和跃动的光斑时，突然想通了。
于是很快写下了算法，完全依照函数的结构，只保留必须要保留的值，相比参考答案，更简洁明了，更具有普遍性.