【 聲明:版權所有,歡迎轉載,請勿用於商業用途。 聯系信箱:feixiaoxing @163.com】
其實編程的朋友知道,不管學什麼語言,循環和遞歸是兩個必須學習的內容。當然,如果循環還好理解一點,那麼遞歸卻沒有那麼簡單。我們曾經對遞歸諱莫如深,但是我想告訴大家的是,遞歸其實沒有那麼可怕。所謂的遞歸就是函數自己調用自己而已,循環本質上也是一種遞歸。
1)求和遞歸函數
我們可以舉一個循環的例子,前面我們說過,如果編寫一個1到n的求和函數怎麼寫呢,你可能會這麼寫:
int calculate(int m)
{
int count = 0;
if(m <0)
return -1;
for(int index = 0; index <= m; index++)
count += index;
return count;
}
int calculate(int m)
{
int count = 0;
if(m <0)
return -1;
for(int index = 0; index <= m; index++)
count += index;
return count;
} 上面只是一個示范。下面我們看看如果是遞歸應該怎麼寫呢?
int calculate(int m)
{
if(m == 0)
return 0;
else
return calculate(m -1) + m;
}
int calculate(int m)
{
if(m == 0)
return 0;
else
return calculate(m -1) + m;
} 大家看著兩段代碼有什麼不同?
(1)第一段代碼從0,開始計算,從0到m逐步計算;第二段代碼是從10開始計算,逐步到0之後這回,這樣同樣可以達到計算的效果
(2)第一段代碼不需要重復的壓棧操作,第二段需要重復的函數操作,當然這也是遞歸的本質
(3)第一段代碼比較長,第二段代碼較短
2)查找遞歸函數
大家可能說,這些代碼有些特殊。如果是查找類的函數,有沒有可能修改成遞歸函數呢?
int find(int array[], int length, int value)
{
int index = 0;
if(NULL == array || 0 == length)
return -1;
for(; index < length; index++)
{
if(value == array[index])
return index;
}
return -1;
}
int find(int array[], int length, int value)
{
int index = 0;
if(NULL == array || 0 == length)
return -1;
for(; index < length; index++)
{
if(value == array[index])
return index;
}
return -1;
}
大家可能說,這樣的代碼可能修改成這樣的代碼:
int _find(int index, int array[], int length, int value)
{
if(index == length)
return -1;
if(value == array[index])
return index;
return _find(index + 1, array, length, value);
}
int find(int array[], int length, int value)
{
if(NULL == array || length == 0)
return -1;
return _find(0, array, length, value);
}
int _find(int index, int array[], int length, int value)
{
if(index == length)
return -1;
if(value == array[index])
return index;
return _find(index + 1, array, length, value);
}
int find(int array[], int length, int value)
{
if(NULL == array || length == 0)
return -1;
return _find(0, array, length, value);
}
3) 指針變量遍歷
結構指針是我們喜歡的遍歷結構,試想如果有下面定義的數據結構:
typedef struct _NODE
{
int data;
struct _NODE* next;
}NODE;
typedef struct _NODE
{
int data;
struct _NODE* next;
}NODE; 那麼,此時我們需要對一個節點鏈接中的所有數據進行打印,應該怎麼辦呢?大家可以自己先想想,然後看看我們寫的代碼對不對。
void print(const NODE* pNode)
{
if(NULL == pNode)
return;
while(pNode){
printf("%d\n", pNode->data);
pNode = pNode->next;
}
}
void print(const NODE* pNode)
{
if(NULL == pNode)
return;
while(pNode){
printf("%d\n", pNode->data);
pNode = pNode->next;
}
}
那麼此時如果改成遞歸,那就更簡單了:
void print(const NODE* pNode)
{
if(NULL == pNode)
return;
else
printf("%d\n", pNode->data);
print(pNode->next);
}
void print(const NODE* pNode)
{
if(NULL == pNode)
return;
else
printf("%d\n", pNode->data);
print(pNode->next);
}
其實,寫這麼多,就是想和大家分享一下我個人的觀點:循環是一種特殊的遞歸,只有遞歸和堆棧是等價的。所有的遞歸代碼都可以寫成堆棧的形式,下面的一片博客我們就討論一下堆棧和遞歸的關系。要想寫好,必須熟練掌握堆棧。