使用局部到整體的思維方式分析遞歸算法示例的教學研究

覃煒達

（河池學院數理學院 廣西·河池 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。