#includestdio.h
我們提供的服務(wù)有:網(wǎng)站制作、成都網(wǎng)站建設(shè)、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、印臺(tái)ssl等。為成百上千家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢和貼心的售后服務(wù),是有科學(xué)管理、有技術(shù)的印臺(tái)網(wǎng)站制作公司
int
power(int
x,int
n)
{
if(n
==
0)
//任何數(shù)的0次方都是1
return
0;
else
if(n
==1)
//如果是1次方
則返回本來(lái)的值
return
x;
else
//否則遞歸循環(huán)
return
x*power(x,n-1);
}
main()
{
printf("%d
",power(3,3));
printf("%d
",power(4,2));
getchar();
return
0;
}
遞歸,是函數(shù)實(shí)現(xiàn)的一個(gè)很重要的環(huán)節(jié),很多程序中都或多或少的使用了遞歸函數(shù)。遞歸的意思就是函數(shù)自己調(diào)用自己本身,或者在自己函數(shù)調(diào)用的下級(jí)函數(shù)中調(diào)用自己。
遞歸之所以能實(shí)現(xiàn),是因?yàn)楹瘮?shù)的每個(gè)執(zhí)行過(guò)程都在棧中有自己的形參和局部變量的拷貝,這些拷貝和函數(shù)的其他執(zhí)行過(guò)程毫不相干。這種機(jī)制是當(dāng)代大多數(shù)程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)子程序結(jié)構(gòu)的基礎(chǔ),是使得遞歸成為可能。假定某個(gè)調(diào)用函數(shù)調(diào)用了一個(gè)被調(diào)用函數(shù),再假定被調(diào)用函數(shù)又反過(guò)來(lái)調(diào)用了調(diào)用函數(shù)。這第二個(gè)調(diào)用就被稱為調(diào)用函數(shù)的遞歸,因?yàn)樗l(fā)生在調(diào)用函數(shù)的當(dāng)前執(zhí)行過(guò)程運(yùn)行完畢之前。而且,因?yàn)檫@個(gè)原先的調(diào)用函數(shù)、現(xiàn)在的被調(diào)用函數(shù)在棧中較低的位置有它獨(dú)立的一組參數(shù)和自變量,原先的參數(shù)和變量將不受影響,所以遞歸能正常工作。程序遍歷執(zhí)行這些函數(shù)的過(guò)程就被稱為遞歸下降。
程序員需保證遞歸函數(shù)不會(huì)隨意改變靜態(tài)變量和全局變量的值,以避免在遞歸下降過(guò)程中的上層函數(shù)出錯(cuò)。程序員還必須確保有一個(gè)終止條件來(lái)結(jié)束遞歸下降過(guò)程,并且返回到頂層。
/*用c語(yǔ)言中的函數(shù)遞歸調(diào)用算法實(shí)現(xiàn)n階矩陣的n次冪*/
#include?stdio.h
#include?stdlib.h
#include?time.h
#include?string.h
//創(chuàng)建矩陣,矩陣用一維數(shù)組存儲(chǔ)
double?*matCreate(unsigned?int?m,?unsigned?int?n)
{
double?*p?=?(double?*)malloc(sizeof(double)?*?m?*?n);
if?(p?==?NULL)?printf("創(chuàng)建矩陣失??!\n");
return?p;
}
//輸入矩陣元素
void?matInput(double?*a,?unsigned?int?m,?unsigned?int?n)
{
for?(int?i?=?0;?i??m;?++i)
{
for?(int?j?=?0;?j??n;?++j)
{
scanf("%f?",?a[i?*?n?+?j]);
}
}
return;
}
//隨機(jī)產(chǎn)生矩陣元素,均勻分布于[from?to]
void?matInitRand(double?*a,?unsigned?int?m,?unsigned?int?n,?double?from,?double?to)
{
if?(a?==?NULL?||?m?=?0?||?n?=?0)?return;
double?x;
srand(time(NULL));
for?(int?i?=?0;?i??m;?++i)
{
for?(int?j?=?0;?j??n;?++j)
{
x?=?(1.0?*?rand()?/?RAND_MAX)?*?(to?-?from)?+?from;
a[i?*?n?+?j]?=?x;
}
}
return;
}
//轉(zhuǎn)置
void?matTranspose(double?*a,?double?*b,?unsigned?int?m,?unsigned?int?n)
{
for?(int?i?=?0;?i??m;?++i)
{
for?(int?j?=?0;?j??n;?++j)
{
b[j*n?+i]=a[i?*?n?+?j]?;
}
}
}
//輸出矩陣
void?matPrint(double?*a,?unsigned?int?m,?unsigned?int?n)
{
for?(int?i?=?0;?i??m;?++i)
{
for?(int?j?=?0;?j??n;?++j)
{
printf("%8.4f?",?a[i?*?n?+?j]);
}
putchar('\n');
}
return;
}
//矩陣乘法c=a*b
void?matMul(double?*a,??double?*b,?double?*c,?unsigned?int?m,?unsigned??int?n,?unsigned?int?k)
{
if?(a?==?NULL?||?b?==?NULL?||?c?==?NULL?||?m?=?0?||?n?=?0?||?k?=?0)????return;
double?x?=?0.0f;
for?(int?i?=?0;?i??m;?++i)
{
for?(int?u?=?0;?u??k;?++u)
{
x?=?0.0f;
for?(int?j?=?0;?j??n;?++j)
{
x?+=?a[i?*?n?+?j]?*?b[j?*?k?+?u];
}
c[i?*?k?+?u]?=?x;
}
}
return;
}
//b=a^n,?a:m*m階矩陣
void?matFac(double?*a,?double?*b,?unsigned?int?n,?unsigned?int?m)
{
double?*c?=?(double?*)malloc(sizeof(double)?*?m?*?m);?//保存臨時(shí)結(jié)果
if?(n??1)
{
matFac(a,?c,?n?-?1,?m);
matMul(a,?c,?b,?m,?m,?m);
}
else
memcpy(b,?a,?sizeof(double)*m?*?m);
//?printf("%d:\n",n);
//?matPrint(b,?m,m);
free(c);????????????????????????????????????//回收內(nèi)存
return?;
}
#define?M?3
#define?N?4
#define?K?N
int?main(int?argc,?char?const?*argv[])
{
double?*A,?*B,?*B1,*BT,?*C;
A?=?matCreate(M,?N);
B?=?matCreate(N,?K);
B1?=?matCreate(N,?K);
BT?=?matCreate(K,N);
C?=?matCreate(M,?K);
if?(!A?||?!B?||?!B1?||?!BT?||?!C)?return?-1;
matInitRand(A,?M,?N,?0.0f,?1.0f);
printf("A=\n");
matPrint(A,?M,?N);
matInitRand(B,?N,?K,?0.0f,?1.0f);
printf("B=\n");
matPrint(B,?N,?K);
matTranspose(B,BT,N,K);
printf("B'=\n");
matPrint(BT,?K,N);
matMul(A,?B,?C,?M,?N,?K);
printf("C=A*B\n");
matPrint(C,?M,?N);
matFac(B,?B1,?4,?N);
printf("B^4\n");
matPrint(B1,?N,?K);
return?0;
}
/*x^n的值必須小于32767,否則輸出的就是負(fù)數(shù)。因?yàn)?,int只有這么大,正常的pow函數(shù)應(yīng)該是float型或是double型,參數(shù)也應(yīng)是float或是double型。*/
#include?stdio.h
int?power(int?x,int?n)
{
if?(n1)
{
? ?return?x*power(x,n-1);
}
else
{
? ?if?(n0)
? ? ? ?return?x;
? ?else
? ? ? ? return?1;
}
}
void?main()
{
int?x,n;
printf("input?x,n:");
scanf("%d%d",x,n);
printf("%d",power(x,n));
getch();
clrscr();
}
遞歸方法的概念
類方法成員間允許相互調(diào)用,也可以自己調(diào)用自己。類的方法如果在方法體內(nèi)直接或間接地自己調(diào)用自己就稱為遞歸方法。
遞歸基本思想就是“自己調(diào)用自己”。遞歸方法實(shí)際上體現(xiàn)了“依此類推”、“用同樣的步驟重復(fù)”這樣的思想,它可以用簡(jiǎn)單的程序來(lái)解決某些復(fù)雜的計(jì)算問(wèn)題。
遞歸調(diào)用在完成階乘運(yùn)算、級(jí)數(shù)運(yùn)算、冪指數(shù)運(yùn)算等方面特別有效。
在執(zhí)行遞歸操作時(shí),C#語(yǔ)言把遞歸過(guò)程中的信息保存在堆棧中。如果無(wú)限循環(huán)地遞歸,或者遞歸次數(shù)太多,則產(chǎn)生“堆棧溢出”錯(cuò)誤
例:用遞歸方法求階乘。利用的數(shù)學(xué)公式為n!=n*(n-1)!。當(dāng)n=0時(shí),n!=1。
代碼如下:
public long F(int n)
{
if (n==1)
return 1;
else
return n*F(n-1);
}
設(shè)置四個(gè)變量左邊界l,右邊界r,上邊界u,下邊界d。每調(diào)用一次遞歸在二維數(shù)組中存一層數(shù)據(jù),然后把l加1,r減1,u加1,d減1。lr為遞歸出口。代碼如下:
#include stdio.h
int b[100][100];
void fz(int l,int r,int u,int d,int v,int n)
{
int x,y,i,j,k,m;
if(lr)
for (x=0;xn;x++)
{
for (y=0;yn;y++)
printf("%4d",b[x][y]);
printf("\n");
}
while(l=r)
{
for (i=l;i=r;i++) b[u][i]=v++;
for (k=u+1;kd;k++) b[k][r]=v++;
for (j=r;jl;j--) b[d][j]=v++;
for (m=d;mu;m--) b[m][l]=v++;
return fz(l+1,r-1,u+1,d-1,v,n);
}
}
int main()
{
int n;
scanf("%d",n);
fz(0,n-1,0,n-1,1,n);
return 0;
}