联通营业厅服务承诺:对照递归算法和非递归算法的优缺点。

根据代数中的二项式定理，二项式(x+y)n的展开式的系数序列可以表示成
图4-1那样的三角形，其中除每一行最左和最右两个系数等于1以外，其余各数均等于上一
行左右两系数之和。这个系数三角形称作杨辉三角形。

(x+y)0 1
(x+y)1 1 1
(x+y)2 1 2 1
(x+y)3 1 3 3 1
(x+y)4 1 4 6 4 1
(x+y)5 1 5 10 10 5 1
(x+y)6 1 6 15 20 15 6 1
(x+y)7 1 7 21 35 35 21 7 1
(x+y)8 1 8 28 56 70 56 28 8 1
图4-1 杨辉三角形

设C(n,k)表示杨辉三角形中第n行(n≥0)的第k个系数(0≤k≤n)，按照二项式定理，C(n,k)
可递归定义为：
1 (k=0或k=n)
C(n,k)=
C(n-1,k-1)+C(n-1,k) (n>=2)

写出计算C(n,k)的递归算法。
解：
int C(int n,int k)
//求出指数为n的二项展开式中第k项(0<=k<=n)系数的递归算法
{
if(k==0||k==n)
return 1;
else
return C(n-1,k-1)+C(n-1,k);
}

利用二维数组写出计算C(n,k)的非递归算法。
解：
int C1(int n,int k)
//求出指数为n的二项展开式中第k项(0<=k<=n)系数的非递归算法
{
typedef int b[15];
//定义一维整型数组类型[15]为b，其尺寸要大于参数n
b*a=new b[n+1];
//动态分配具有b类型的一维数组，其尺寸为n+1，这样a就指向了一个具有
//[n+1][15]的二维数组。
for(int i=0;i<=n;i++)
for(int j=0;j<=i;j++)
//外循环每循环一次计算出指数为i的二项展开式的所有系数，内循环每循环
//一次计算出此展开式中第j项的系数
if(j==0||j==1)
a[i][j]=1;
else
a[i][j]=a[i-1][j-1]+a[i-1][j];
return a[n][k]; //返回指数为n的二项展开式中第k项的系数
}

分析递归算法和非递归算法的时间复杂度和空间复杂度。
解：
递归时间复杂度和空间复杂度分别为O(2n)和O(n)，非递归算法的时间复杂
度和空间复杂度均为O(n2)。
对照递归算法与非递归算法在杨辉三角中的优缺点