循環(huán)與遞歸的本質(zhì)區(qū)別在于內(nèi)存的使用上，遞歸是方法調(diào)用方法本身，而隨著遞歸的次數(shù)的增加，內(nèi)存的消耗也是不斷增長，而在我們寫代碼時，內(nèi)存是一個很重要的部分，我們盡量都是減少內(nèi)存的消耗，以免造成對系統(tǒng)資源的浪費，循環(huán)占用的內(nèi)存很少，每次循環(huán)都會釋放之前分配的內(nèi)存，但是很多遞歸的功能是不能用循環(huán)實現(xiàn)的，這就要考慮你要實現(xiàn)的功能了，如果非遞歸不可完成的功能，我們也不會刻意更改。
創(chuàng)新互聯(lián)公司從2013年成立，公司自成立以來始終致力于為企業(yè)提供官網(wǎng)建設(shè)、移動互聯(lián)網(wǎng)業(yè)務(wù)開發(fā)（微信平臺小程序開發(fā)、手機網(wǎng)站建設(shè)、重慶APP軟件開發(fā)等），并且包含互聯(lián)網(wǎng)基礎(chǔ)服務(wù)（域名、主機服務(wù)、企業(yè)郵箱、網(wǎng)絡(luò)營銷等）應用服務(wù)；以先進完善的建站體系及不斷開拓創(chuàng)新的精神理念，幫助企業(yè)客戶實現(xiàn)互聯(lián)網(wǎng)業(yè)務(wù)，嚴格把控項目進度與質(zhì)量監(jiān)控加上過硬的技術(shù)實力獲得客戶的一致贊譽。
int count = 0;
void a( void )
{
?0?2 count++;
?0?2 if ( count 100 )
?0?2 a(); // 如果count100, 調(diào)用自己。一直到100就停止！不過遞歸多了耗盡堆棧會崩潰！
}
遞歸算法：是一種直接或者間接地調(diào)用自身的算法。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。
遞歸算法的特點
遞歸過程一般通過函數(shù)或子過程來實現(xiàn)。
遞歸算法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。
遞歸算法的實質(zhì)：是把問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題的解。
遞歸算法解決問題的特點：
(1) 遞歸就是在過程或函數(shù)里調(diào)用自身。
(2) 在使用遞增歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口。
(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設(shè)計程序。
(4) 在遞歸調(diào)用的過程當中系統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計程序。
遞歸算法所體現(xiàn)的“重復”一般有三個要求：
一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半)；
二是相鄰兩次重復之間有緊密的聯(lián)系，前一次要為后一次做準備(通常前一次的輸出就作為后一次的輸入)；
三是在問題的規(guī)模極小時必須用直接給出解答而不再進行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達到直接解答的大小為條件)，無條件遞歸調(diào)用將會成為死循環(huán)而不能正常結(jié)束。
例子如下：
描述：把一個整數(shù)按n(2=n=20)進制表示出來，并保存在給定字符串中。比如121用二進制表示得到結(jié)果為：“1111001”。
參數(shù)說明：s: 保存轉(zhuǎn)換后得到的結(jié)果。
n: 待轉(zhuǎn)換的整數(shù)。
b: n進制（2=n=20）
void
numbconv(char *s, int n, int b)
{
int len;
if(n == 0) {
strcpy(s, "");
return;
}
/* figure out first n-1 digits */
numbconv(s, n/b, b);
/* add last digit */
len = strlen(s);
s[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];
s[len+1] = '\0';
}
void
main(void)
{
char s[20];
int i, base;
FILE *fin, *fout;
fin = fopen("palsquare.in", "r");
fout = fopen("palsquare.out", "w");
assert(fin != NULL fout != NULL);
fscanf(fin, "%d", base);
/*PLS set START and END*/
for(i=START; i = END; i++) {
numbconv(s, i*i, base);
fprintf(fout, "%s\n", s);
}
exit(0);
}
遞歸算法簡析（PASCAL語言）
遞歸是計算機科學的一個重要概念,遞歸的方法是程序設(shè)計中有效的方法,采用遞歸編寫
程序能是程序變得簡潔和清晰.
一 遞歸的概念
1.概念
一個過程(或函數(shù))直接或間接調(diào)用自己本身,這種過程(或函數(shù))叫遞歸過程(或函數(shù)).
如:
procedure a;
begin
.
.
.
a;
.
.
.
end;
這種方式是直接調(diào)用.
又如:
procedure b; procedure c;
begin begin?0?2
. .
. .
. .
c; b;
. .
. .
. .
end; end;
這種方式是間接調(diào)用.
例1計算n!可用遞歸公式如下:
1 當 n=0 時?0?2
fac(n)={n*fac(n-1) 當n0時
可編寫程序如下:
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
例2 樓梯有n階臺階,上樓可以一步上1階,也可以一步上2階,編一程序計算共有多少種不同的走法.
設(shè)n階臺階的走法數(shù)為f(n)
顯然有
1 n=1?0?2
f(n)={
f(n-1)+f(n-2) n2
可編程序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
二，如何設(shè)計遞歸算法
1.確定遞歸公式
2.確定邊界(終了)條件
三，典型例題
例3 梵塔問題
如圖:已知有三根針分別用1,2,3表示,在一號針中從小放n個盤子,現(xiàn)要求把所有的盤子
從1針全部移到3針,移動規(guī)則是:使用2針作為過度針,每次只移動一塊盤子,且每根針上
不能出現(xiàn)大盤壓小盤.找出移動次數(shù)最小的方案.
程序如下:
program fanta;
var
n:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'---',c)
else begin
move(n-1,a,c,b);
writeln(a,'---',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是:先從數(shù)據(jù)序列中選一個元素,并將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1, 處理結(jié)束.
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b;
repeat
while (b[j]=x) and (ji) do j:=j-1;
if ji then begin t1:=b; b:=b[j];b[j]:=t1;end;
while (b=x) and (ij) do i:=i+1;
if ij then begin t1:=b[j];b[j]:=b;b:=t1; end
until i=j;
b:=x;
i:=i+1;j:=j-1;
if sj then quicksort(b,s,j);
if it then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a:6);
writeln;
end.
#includestdio.h
int?account_next(int?a[][8],?int?m,?int?n)
{
//?列索引n執(zhí)行+1，即進入下一列
if?(-1?=?n??n?!=?8)
n++;
//?當列索引n至最后一列時（n=8），行索引m執(zhí)行+1，即進入下一行
else?if?(-1?=?m??m?!=?8)
{
n?=?0;
m++;
}
//?當行索引=8時，說明已經(jīng)遍歷全部元素
else
return?0;
if?(0?=?m??m??8??0?=?n??n??8??a[m][n]?==?0)
{
//?計數(shù)a[m][n]左、右、上、下、左上、左下、右上、右下1的個數(shù)
int?c?=?0;
//?left
if?(0??n??1?==?a[m][n?-?1])?c++;
//?right
if?(7??n??1?==?a[m][n?+?1])?c++;
//?up
if?(0??m??1?==?a[m?-?1][n]) c++;
//?down
if?(7??m??1?==?a[m?+?1][n])?c++;
//?left?up
if?(0??m??0??n??1?==?a[m?-?1][n?-?1]) c++;
//?left?down
if?(7??m??0??n??1?==?a[m?+?1][n?-?1])?c++;
//?right?up
if?(0??m??7??n??1?==?a[m?-?1][n?+?1])?c++;
//?right?down
if?(7??m??7??n??1?==?a[m?+?1][n?+?1]) c++;
printf("a[?%d?][?%d?]?周圍有?%d?個1.\n",?m,?n,?c);
}
//?計數(shù)a[m][n]下一個元素
account_next(a,?m,?n);
}
int?main(void)
{
int?a[8][8]?=?{
{?1,?1,?1,?1,?1,?1,?1,?1?},
{?1,?1,?0,?0,?1,?0,?0,?1?},
{?1,?0,?0,?1,?0,?0,?1,?1?},
{?1,?1,?1,?0,?0,?1,?0,?1?},
{?1,?0,?1,?1,?1,?0,?0,?1?},
{?1,?1,?0,?0,?0,?1,?1,?1?},
{?1,?1,?1,?1,?0,?0,?0,?1?},
{?1,?1,?1,?1,?1,?1,?1,?1?}?};
account_next(a,?0,?-1);
return?0;
}
遞歸是函數(shù)體中調(diào)用自己，如果不加控制，將無休止的調(diào)用自己，直到堆棧溢出。循環(huán)是反復執(zhí)行某一段區(qū)域內(nèi)的代碼，如果不加控制，就會形成死循環(huán)。所以不管是遞歸還是循環(huán)，都要設(shè)定一定的條件，以結(jié)束遞歸或循環(huán)。
實際問題中，有一些問題是遞歸的，這樣的問題使用遞歸程序解決感覺會自然些，程序也會簡單些，但是，遞歸要經(jīng)常調(diào)用函數(shù)，開銷（內(nèi)存、時間）大，有些問題就不適宜使用，循環(huán)不需要調(diào)用自身，甚至可以不調(diào)用函數(shù)，效率高，不過，要將遞歸問題改成非遞歸，可能就要動動腦筋。
上例中pow2
函數(shù)實現(xiàn)部分指數(shù)計算功能，(b,
n-1)
＝3
這個提法有問題，因為遞歸調(diào)用時，在返回之前系統(tǒng)堆棧上有一大堆（從第一次調(diào)用知道條件滿足時的次數(shù)）的該遞歸函數(shù)，條件滿足后這一系列的函數(shù)依次返回。上述函數(shù)運行過程是這樣的：
執(zhí)行主函數(shù)的
pow2(3,
2);
后：
1：
b
=
3
n
=
2
此時
n
0;
pow2
調(diào)用自身（即遞歸調(diào)用）：
pow2(b,
n-1)
*
b
后：
2：
b
=
3
n
=
1
此時
n
0;
pow2
調(diào)用自身（即遞歸調(diào)用）：
pow2(b,
n-1)
*
b
后：
3：
b
=
3
n
=
此時
n
=
0,
if
(n
=
0)
條件滿足
1;
遞歸函數(shù)第一次（函數(shù)最后依次遞歸調(diào)用）返回，值為
1
4：
上一次
pow2(b,
n-1)
返回值為
1，return
pow2(b,
n-1)
*
b;
所以本次（第2次）返回
3
5：
上一次
pow2(b,
n-1)
返回值為
3，return
pow2(b,
n-1)
*
b;
所以本次（第1次）返回
9
6：
函數(shù)main得到
pow2
的返回值
9
重慶分公司
重慶分公司
