【背景】
已知f为单链表的表头指针，链表中存储的是整形数据，试写出实现下列运算的递归算法：
1、求链表中的最大整数
2、求链表的节点个数
3、求所有整数的平均值
【源码运行环境】
操作系统：Windows 10
编译环境：Dev C++(基于C99标准）
【思路】
1、构造递归体结束条件（当前访问的节点为NULL）
2、构造递归体操作
3、尽可能使用尾递归操作
【源码实现】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | /**方法名：findMax*作用：递归查找链表中的最大值 *参数：链表指针 l， 最大值指针 max ; *返回值：void*Author: WellLee*Last Modified: 2018-12-13 13:28:30*/void findMax(Link l, int *max){ Link temp = l; if(temp == NULL) { return; } if(temp->elem > *max) { *max = l->elem; } findMax(temp->next, max);}/**方法名：getLength1*作用：递归求链表长度 *参数：链表指针 l， 长度指针 length ; *返回值：void*Author: WellLee*Last Modified: 2018-12-13 13:28:30*/void getLength1(Link l, int *length){ Link temp = l; if(temp == NULL) { return; } *length += 1; getLength1(temp->next, length);}/**方法名：average*作用：递归求所有整数的平均值 *参数：链表指针 l，计数器：total, 平均值指针：avg, 链表长度: i ; *返回值：void*Author: WellLee*Last Modified: 2018-12-13 13:28:30*/void average(Link l, int total, float *avg, int i){ Link temp = l; if(temp == NULL) { *avg = (float)(total) / i; return; } total += temp->elem; average(temp->next, total, avg, i + 1);} |
【总结】
递归的方法有很多，尾递归是一种能够在一定程度上减低空间复杂度的递归算法。
【参考文献】
-
《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社