一步一步寫算法（之循環和遞歸）

【 聲明：版權所有，歡迎轉載，請勿用於商業用途。  聯系信箱：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);
}
    其實，寫這麼多，就是想和大家分享一下我個人的觀點：循環是一種特殊的遞歸，只有遞歸和堆棧是等價的。所有的遞歸代碼都可以寫成堆棧的形式，下面的一片博客我們就討論一下堆棧和遞歸的關系。要想寫好，必須熟練掌握堆棧。