这几天正在复习一些基本的算法和实现,今天看了看递归的基本原理,发现自己对递归还不是特别清楚,特别是不清楚递归的思想,不能很准确的把握先分解成小事件,在合并的思想,其实也是数学归纳法的程序体现,其实数学归纳法是一种强大的方法,记得高中的时候最喜欢做的题目就是数学归纳方面的证明,现在想过来好多问题我不能采用这种方式思考,可见知识真的是有联系的,只是我们没有找到联系的方式而已。
为了熟悉递归的思想,我尝试了采用递归的方式实现单向链表的基本操作。单向的链表是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),这样逐层的分解,分解成很多相似的小事件,当最小的事件解决完成以后,就能解决高层次的事件,这种逐层分解,逐层合并的方式就构成了递归的思想,最主要的要找到递归的出口和递归的方式,搞清楚了这两个,实现一个递归问题相对来说就比较简单啦。
但是递归也存在问题,特别是深层次的递归可能导致栈空间的溢出,因为堆栈空间的大小并不是无限大的,特别当递归中数据量特别大的情况下,递归很有可能导致栈空间的溢出,因此递归并不是万能的,但是递归确实是一种思考问题的方式,一种反向思考的形式,从结果到具体的小过程。当然具体的问题就要具体分析啦。
用一句简单的话记住递归就是:我完成最简单的那一步,其他的复杂的相似问题都找别人去做吧。
阅读(518) | 评论(0) | 转发(0) |