程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法(之循環和遞歸)

一步一步寫算法(之循環和遞歸)

編輯:關於C語言

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved