使用局部到整体的思维方式分析递归算法示例的教学研究

覃炜达

（河池学院数理学院 广西·河池 546300）

0 引言

《算法设计与分析》是信息与计算科学、统计学、计算机科学与技术、大数据等专业基础课。对于该门课程，递归算法扮演重要角色，提高学生分析递归算法示例的能力，对于提高该门课程的教学质量尤为重要。使用局部到整体的思维方式也是分析递归算法的一种重要的教学方法，文献[5]使用局部到整体的思维方式对解数组最大值、次大值算法示例进行教学初步探究，主要是通过减少数组的元素，从而降低递归执行的次数，复杂的程序执行过程实现简单化，加深学生对算法的理解。对于具有复杂嵌套函数的递归算法示例，按照文献[5]的方法，单单减少数组的元素，虽然降低递归执行的次数，由于递归函数中有复杂的内嵌函数，复杂的嵌套函数执行过程还是没法实现简单化。本文在文献[5]工作基础上，对于具有复杂的嵌套函数递归算法使用局部到整体的思维方式的教学方式进行更进一步研究，不仅考虑减少数组的元素，还要考虑对复杂的嵌套函数进行优化，从而使得复杂的程序执行过程实现简单化，并通过具体的算法示例说明教学过程。

1 具有嵌套函数的递归算法示例

问题描述：分析以下递归算法，并写出程序运行结果。

程序代码如下：

2 算法结构分析及使用局部到整体的思维方式分析递归算法示例的教学过程

算法结构分析：

程序需要调用函数，且递归函数中有使用嵌套函数。

由于算法结构复杂，主函数中数组元素个数较多，则函数重复调用次数就变多，并且递归函数中内嵌复杂函数，导致学生不易理解算法的执行步骤。如果数组元素减少，递归函数内嵌复杂函数优化了，复杂的问题就变为简单了，学生就能更好的理解算法的实现过程。如何优化嵌套函数使得优化后的代码简单了？观察嵌套函数

返回值都是z+6，学生不易理解。可以把返回值由z+6改为z，优化嵌套函数后完整的代码如下：

优化后的代码与所研究的代码相比较，不仅简单化了，而且优化后的代码还是学生所学过的知识点——用递归法求一个整数数组a的最大元素，参见文献[1]。把陌生的代码变为熟悉的代码，把复杂的代码变为相对简单的代码，说明改进后代码的优化效果比较好。

授课中，教师按照局部到整体的思维方式对优化后的代码进行分析，结合对优化后的代码的分析结果，按照局部到整体的思维方式对所研究的代码进行分析，每次分析算法之后的当场调试程序进行验证，就能使学生很好地理解算法的实现过程，具体的教学过程如下：

第一次改进算法：在主函数设置数组改为a[]={0}，fmax(a,4)改为 fmax(a,1)，return(z+6)改为 return(z)，其它语句不变。

算法的执行步骤如下：

1-1实参数组fmax(a,1)传递给形参数组intfmax(inta[],int i)。传递之后，在 fmax(int a[],int i)中，a[]={0}，i=1。

1-2比较i==1为真，执行return a[0]，其中a[0]为0。

1-3返回主函数，fmax(a,1)得到返回值0。

第二次改进算法：在主函数设置数组改为a[]={0,3}，fmax(a,4)改为 fmax(a,2)，return(z+6)改为 return(z)，其它语句不变。

算法的执行步骤如下：

2-1实参数组fmax(a,2)传递给形参数组intfmax(inta[],int i)。传递之后，在 fmax(int a[],int i)中，a[]={0,3}，i=2。

2-2比较i==1为假，执行return(max(fmax(a,1),a[1]))，其中通过调用内嵌递归函数得到返回值3。

2-3返回主函数，fmax(a,2)得到返回值3。

第三次改进算法：在主函数设置数组改为a[]={0,3,5}，fmax(a,4)改为fmax(a,3)，在函数设置return(z+6)改为return(z)，其它语句不变。

算法的执行步骤如下：

3-1实参数组fmax(a,3)传递给形参数组intfmax(inta[],int i)。传递之后，在 fmax(int a[],int i)中，a[]={0,3,5}，i=3。

3-2比较i==1为假，执行return(max(fmax(a,2),a[2]))，其中通过调用内嵌递归函数得到返回值5。

3-3返回主函数，fmax(a,3)得到返回值5。

第四次改进算法：在函数设置return(z+6)改为return(z)，其它语句不变。

算法的执行步骤如下：

4-1实参数组fmax(a,4)传递给形参数组intfmax(inta[],int i)。传递之后，在 fmax(int a[],int i)中，a[]={0,3,5,6}，i=4。

4-2比较i==1为假，执行return(max(fmax(a,3),a[3]))，其中通过调用内嵌递归函数得到返回值6。

4-3返回主函数，fmax(a,4)得到返回值6。

第五次改进算法：在主函数设置数组改为a[]={0}，fmax(a,4)改为fmax(a,1)，其它语句不变。

算法的执行步骤如下：

5-1实参数组fmax(a,1)传递给形参数组intfmax(inta[],int i)。传递之后，在 fmax(int a[],int i)中，a[]={0}，i=1。

5-2比较i==1为真，执行return a[0]，其中a[0]为0。

5-3返回主函数，fmax(a,1)得到返回值0。

第六次改进算法：在主函数设置数组改为a[]={0,3}，fmax(a,5)改为fmax(a,2)，其它语句不变。

算法的执行步骤如下：

6-1实参数组fmax(a,2)传递给形参数组intfmax(inta[],int i)。传递之后，在 fmax(int a[],int i)中，a[]={0,3}，i=2。

6-2比较i==1为假，执行return(max(fmax(a,1),a[1]))，其中通过调用内嵌递归函数得到返回值9。强调此步骤与2-2类似，在2-2中，学生已经理解返回值Z为3，此处的返回值为Z+6，此处Z与2-2中Z的值不一定相同，需要更进一步分析。根据5-3所知fmax(a,1)等于0，而此处的Z等于fmax(a,1)与a[1]的最大值，即此处Z为3，则Z+6=9。

6-3返回主函数，fmax(a,2)得到返回值9。

第七次改进算法，在主函数设置数组改为a[]={0,3,5}，fmax(a,4)改为fmax(a,3)，其它语句不变。

算法的执行步骤如下：

7-1实参数组fmax(a,3)传递给形参数组intfmax(inta[],int i)。传递之后，在 fmax(int a[],int i)中，a[]={0,3,5}，i=3。

7-2比较i==1为假，执行return(max(fmax(a,2),a[2]))，其中通过调用内嵌递归函数得到返回值15。强调此步骤与3-2类似，在3-2中，学生已经理解返回值Z为3，此处的返回值为Z+6，此处Z与3-2中Z的值不一定相同，需要更进一步分析。根据6-3所知fmax(a,2)等于9，而此处的Z等于fmax(a,2)与a[2]的最大值，即此处Z为9，则Z+6=15。

7-3返回主函数，fmax(a,3)得到返回值15。

第八次不改进算法，语句不变。

算法的执行步骤如下：

8-1实参数组fmax(a,4)传递给形参数组intfmax(inta[],int i)。传递之后，在 fmax(int a[],int i)中，a[]={0,3,5,6}，i=4。

8-2比较i==1为假，执行return(max(fmax(a,3),a[3]))，其中通过调用内嵌递归函数得到返回值21。强调此步骤与4-2类似，在4-2中，学生已经理解返回值Z为6，此处的返回值为Z+6，此处Z与4-2中Z的值不一定相同，需要更进一步分析。根据7-3所知fmax(a,3)等于15，而此处的Z等于fmax(a,2)与a[3]的最大值，即此处Z为15，则Z+6=21。

8-3返回主函数，fmax(a,3)得到返回值21。