【背景】

已知f为单链表的表头指针，链表中存储的是整形数据，试写出实现下列运算的递归算法：

1、求链表中的最大整数

2、求链表的节点个数

3、求所有整数的平均值

【源码运行环境】

操作系统：Windows 10

编译环境：Dev C++(基于C99标准)

【思路】

1、构造递归体结束条件(当前访问的节点为NULL)

2、构造递归体操作

3、尽可能使用尾递归操作

【源码实现】

/*

*方法名：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);

}

【总结】

递归的方法有很多，尾递归是一种能够在一定程度上减低空间复杂度的递归算法。

【参考文献】

《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社