這幾天正在復(fù)習(xí)一些基本的算法和實(shí)現(xiàn)，今天看了看遞歸的基本原理，發(fā)現(xiàn)自己對(duì)遞歸還不是特別清楚，特別是不清楚遞歸的思想，不能很準(zhǔn)確的把握先分解成小事件，在合并的思想，其實(shí)也是數(shù)學(xué)歸納法的程序體現(xiàn)，其實(shí)數(shù)學(xué)歸納法是一種強(qiáng)大的方法，記得高中的時(shí)候最喜歡做的題目就是數(shù)學(xué)歸納方面的證明，現(xiàn)在想過(guò)來(lái)好多問(wèn)題我不能采用這種方式思考，可見(jiàn)知識(shí)真的是有聯(lián)系的，只是我們沒(méi)有找到聯(lián)系的方式而已。
為了熟悉遞歸的思想，我嘗試了采用遞歸的方式實(shí)現(xiàn)單向鏈表的基本操作。單向的鏈表是C語(yǔ)言課程中接觸到的中比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，但是他確實(shí)其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，在一般情況下都是采用迭代的形式實(shí)現(xiàn)，迭代的形式相比遞歸要節(jié)省時(shí)間和空間，但是代碼相對(duì)來(lái)說(shuō)要復(fù)雜，遞歸往往只是簡(jiǎn)單的幾句代碼，我主要是為了熟悉迭代，并不在性能上進(jìn)行分析。
基本的實(shí)現(xiàn)如下所示：
#include<stdio.h>
#include<stdlib.h>
typedef struct listnode
{
int val;
struct listnode *next;
}List;
/*統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)*/
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);
}
}
/*刪除一個(gè)節(jié)點(diǎn)的數(shù)據(jù)為d的節(jié)點(diǎn)*/
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的節(jié)點(diǎn)*/
List* delete_allnode(List *head, int d)
{
List *temp = head, *cur = head;
if(head != NULL)
{
/*如果第一個(gè)就是需要?jiǎng)h除的對(duì)象*/
if(cur->val == d)
{
temp = cur;
cur = cur->next;
free(temp);
temp = NULL;
temp = delete_allnode(cur, d);
head = temp;
}
else /*不是刪除的對(duì)象*/
{
cur = head->next;
temp = delete_allnode(cur, d);
/*將得到的鏈表連接到檢測(cè)的區(qū)域*/
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;
}
}
/*創(chuàng)建鏈表*/
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;
}
/*插入節(jié)點(diǎn)*/
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;
}
遞歸中需要注意的思想我任務(wù)就是為了解決當(dāng)前的問(wèn)題，我完成最簡(jiǎn)單的一部操作，其他的由別人去完成，比如漢諾塔中的第一個(gè)和尚讓第二個(gè)和尚把前63個(gè)金盤放在B處，而他自己只需要完成從A到C的搬運(yùn)，實(shí)質(zhì)上他自己完成的只有一部最簡(jiǎn)答的，但是搬運(yùn)這種動(dòng)作有存在非常大的相似性。
因此為了解決當(dāng)前的問(wèn)題f(n),就需要解決問(wèn)題f(n-1),而f(n-1)的解決就需要解決f(n-2)，這樣逐層的分解，分解成很多相似的小事件，當(dāng)最小的事件解決完成以后，就能解決高層次的事件，這種逐層分解，逐層合并的方式就構(gòu)成了遞歸的思想，最主要的要找到遞歸的出口和遞歸的方式，搞清楚了這兩個(gè)，實(shí)現(xiàn)一個(gè)遞歸問(wèn)題相對(duì)來(lái)說(shuō)就比較簡(jiǎn)單啦。
但是遞歸也存在問(wèn)題，特別是深層次的遞歸可能導(dǎo)致�？臻g的溢出，因?yàn)槎褩？臻g的大小并不是無(wú)限大的，特別當(dāng)遞歸中數(shù)據(jù)量特別大的情況下，遞歸很有可能導(dǎo)致�？臻g的溢出，因此遞歸并不是萬(wàn)能的，但是遞歸確實(shí)是一種思考問(wèn)題的方式，一種反向思考的形式，從結(jié)果到具體的小過(guò)程。當(dāng)然具體的問(wèn)題就要具體分析啦。
用一句簡(jiǎn)單的話記住遞歸就是：我完成最簡(jiǎn)單的那一步，其他的復(fù)雜的相似問(wèn)題都找別人去做吧。