這幾天正在復習一些基本的算法和實現，今天看了看遞歸的基本原理，發現自己對遞歸還不是特別清楚，特別是不清楚遞歸的思想，不能很準確的把握先分解成小事件，在合并的思想，其實也是數學歸納法的程序體現，其實數學歸納法是一種強大的方法，記得高中的時候最喜歡做的題目就是數學歸納方面的證明，現在想過來好多問題我不能采用這種方式思考，可見知識真的是有聯系的，只是我們沒有找到聯系的方式而已。
為了熟悉遞歸的思想，我嘗試了采用遞歸的方式實現單向鏈表的基本操作。單向的鏈表是C語言課程中接觸到的中比較復雜的數據結構，但是他確實其他數據結構的基礎，在一般情況下都是采用迭代的形式實現，迭代的形式相比遞歸要節省時間和空間，但是代碼相對來說要復雜，遞歸往往只是簡單的幾句代碼，我主要是為了熟悉迭代，并不在性能上進行分析。
基本的實現如下所示：
#include<stdio.h>
#include<stdlib.h>
typedef struct listnode
{
int val;
struct listnode *next;
}List;
/*統計節點個數*/
int count_listnode(List *head)
{
static int count = 0;
if(NULL != head)
{
count += 1;
if(head->next != NULL)
{
count_listnode(head->next);
}
return count;
}
}
/*順序打印*/
void fdprint_listnode(List *head)
{
if(NULL != head)
{
printf("%d\t",head->val);
if(head->next != NULL)
{
fdprint_listnode(head->next);
}
}
}
/*反向打印*/
void bkprint_listnode(List *head)
{
if(head != NULL)
{
if(head->next != NULL)
{
bkprint_listnode(head->next);
}
printf("%d\t",head->val);
}
}
/*刪除一個節點的數據為d的節點*/
List *delete_node(List * head, int d)
{
List *temp = head;
if(head != NULL)
{
if(head->val == d)
{
temp = head;
head = head->next;
free(temp);
temp = NULL;
}
else
{
temp = head->next;
if(temp != NULL)
{
temp = delete_node(temp,d);
head->next = temp;
}
}
}
return head;
}
/*刪除所有val = d的節點*/
List* delete_allnode(List *head, int d)
{
List *temp = head, *cur = head;
if(head != NULL)
{
/*如果第一個就是需要刪除的對象*/
if(cur->val == d)
{
temp = cur;
cur = cur->next;
free(temp);
temp = NULL;
temp = delete_allnode(cur, d);
head = temp;
}
else /*不是刪除的對象*/
{
cur = head->next;
temp = delete_allnode(cur, d);
/*將得到的鏈表連接到檢測的區域*/
head->next = temp;
}
}
return head;
}
/*最大值*/
int max_list(List *head)
{
int max = 0;
int temp;
if(NULL == head)
{
printf("Error: NULL pointer...");
}
if(NULL != head && head->next == NULL)
{
return head->val;
}
else
{
temp = max_list(head->next);
max = (head->val > temp ? head->val : temp);
return max;
}
}
/*最小值*/
int min_list(List *head)
{
int min = 0;
int temp;
if(NULL == head)
{
printf("Error: NULL pointer...");
}
if(NULL != head && head->next == NULL)
{
return head->val;
}
else
{
temp = min_list(head->next);
min = (head->val < temp ? head->val : temp);
return min;
}
}
/*創建鏈表*/
List* create_list(int val)
{
List *head = (List *)malloc(sizeof(List)/sizeof(char));
if(NULL == head)
{
return NULL;
}
head->val = val;
head->next = NULL;
return head;
}
/*插入節點*/
List* insert_listnode(List *head, int val)
{
List *temp;
if(NULL == head)
{
return NULL;
}
temp = (List *)malloc(sizeof(List)/sizeof(char));
temp->val = val;
temp->next = head;
head = temp;
return head;
}
/*刪除鏈表*/
void delete_list(List *head)
{
List *temp = NULL;
if(head != NULL)
{
temp = head;
head = head->next;
free(temp);
temp = NULL;
delete_list(head);
}
}
int main()
{
int n = 0;
int i = 0;
List * head = create_list(10);
for(i = 0; i < 10; ++ i)
{
n = 1 + (int)(10.0*rand()/(RAND_MAX + 1.0));
head = insert_listnode(head, n);
}
fdprint_listnode(head);
printf("\n");
bkprint_listnode(head);
printf("\n%d\n", count_listnode(head));
printf("\n");
#if 10
head = delete_node(head, 10);
fdprint_listnode(head);
printf("\n");
bkprint_listnode(head);
printf("\n");
#endif
#if 10
head = delete_allnode(head, 10);
fdprint_listnode(head);
printf("\n");
bkprint_listnode(head);
#endif
printf("max = %d\n",max_list(head));
printf("max = %d\n",min_list(head));
delete_list(head);
head = NULL;
if(head == NULL)
{
printf("ERROR:null pointer!...\n");
}
return 0;
}
遞歸中需要注意的思想我任務就是為了解決當前的問題，我完成最簡單的一部操作，其他的由別人去完成，比如漢諾塔中的第一個和尚讓第二個和尚把前63個金盤放在B處，而他自己只需要完成從A到C的搬運，實質上他自己完成的只有一部最簡答的，但是搬運這種動作有存在非常大的相似性。
因此為了解決當前的問題f(n),就需要解決問題f(n-1),而f(n-1)的解決就需要解決f(n-2)，這樣逐層的分解，分解成很多相似的小事件，當最小的事件解決完成以后，就能解決高層次的事件，這種逐層分解，逐層合并的方式就構成了遞歸的思想，最主要的要找到遞歸的出口和遞歸的方式，搞清楚了這兩個，實現一個遞歸問題相對來說就比較簡單啦。
但是遞歸也存在問題，特別是深層次的遞歸可能導致棧空間的溢出，因為堆�？臻g的大小并不是無限大的，特別當遞歸中數據量特別大的情況下，遞歸很有可能導致棧空間的溢出，因此遞歸并不是萬能的，但是遞歸確實是一種思考問題的方式，一種反向思考的形式，從結果到具體的小過程。當然具體的問題就要具體分析啦。
用一句簡單的話記住遞歸就是：我完成最簡單的那一步，其他的復雜的相似問題都找別人去做吧。