递归函数求x的n次方,求x的n次方的递归函数

求x的n次方–递归算法 #include<stdio.h>int power(int x,int n){int y;if(n==0) y=1;else {y=power(x,n/2);y=y*y;if(n%2==1)y=y*x;}return y;}void main(){int a,b;printf("请输入底数与次幂：");scanf("%d%dn",&a,&b);int sum;sum=power(a,b);printf("结果为：%dn",sum);}

分析：过程分为两种，当n为偶数，则Xn=〖〖(X〗(n/2))〗2；如果n为奇数，则Xn=X*〖〖(X〗(n/2))〗2；则f(1)=1,f(n)=f(n/2)+1；令n=2k，g(k)=f(2k)，那么可以得到g(0)=1，g(k)=f(k-1)+1，推出时间复杂度为：O_((logn))