遞歸算法課堂教學設計探討

王琳 張學波

摘要：結合大學計算機基礎課程的開設情況，針對課程中一些不易理解且難以講解的知識點，如遞歸算法，本文結合遞歸算法經典示例漢諾塔問題，探討了一個新的課堂教學設計，并應用于實際的教學中。首先如何引入課堂，抓住學生的興趣，然后提出問題，思考遞歸算法和漢諾塔之間的關系，并通過互動環節，讓學生動手嘗試挪動漢諾模型，學會使用計算思維進行思考與分析。最后依據遞歸原理，用Python語言編寫漢諾塔的遞歸函數。在實際教學過程中，該課堂設計提高了學員學習的主動性和參與度，提升了課堂教學質量和學員的計算思維能力。

關鍵詞：課堂設計;遞歸算法;漢諾塔問題;可視化;turtle

中圖分類號：TP311? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）27-0208-02

“大學計算機基礎”是大學本科教育的第一門計算機公共基礎課程，課程的主要目的是從計算機應用、計算機系統理解和計算思維培養三個方面提高學生的計算機應用能力。從2008年開始，以“計算思維”的培養為主線開展計算科學通識教育，逐漸成為國內外計算機基礎教育界的共識。

基于這種共識，“大學計算機課程”選擇Python作為實踐語言，將信息編碼、微機原理、操作系統、網絡、數據庫等知識既作為教學內容，又作為計算思維求解問題的研究對象加以實踐。希望通過這種問題求解的學習和實踐過程，在培養學生理解計算機基礎知識的同時，能有意識地將計算思維的方法和技能運用在各自專業的學習中，能解決具有一定難度的實際問題。

作為課程的重難點之一的第三章，即計算思維這一章，要求學生在理解計算思維的同時，要了解一些典型算法，并能夠掌握典型算法的Python實現方法。本文以遞歸算法為例，探討如何更好地進行課堂設計。

遞歸算法作為經典算法之一，雖然實現較容易，但理解起來有一定的難度，為了讓學生能更直觀的理解遞歸算法，課程專門設置了一個遞歸算法經典示例漢諾塔問題，利用Python的turtle庫實現漢諾塔的可視化，幫助學生從抽象的理論思維過渡到直觀的可視化應用。

1 如何引入課堂

教師在講解漢諾塔問題之前，可以借助動畫的形式展現可視化的漢諾塔，便于較快地抓住學生的注意力，提高學習興趣;引導學生在觀看動畫的同時，思考漢諾塔中的每個盤片是怎樣移動的？利用Python語言如何編寫程序實現它的可視化效果？

帶著這些問題，教師引出漢諾塔問題的傳說和移動規則。漢諾塔問題來源于一個古老的傳說， 傳說印度教里有一個神叫梵天，梵天在創造世界的時候做了三根金剛石柱子，其中在 1號柱子按大小順序套著64個黃金盤片，梵天要求僧侶們把這64個盤片借助于中間的2號柱子移到3號柱子上，按原來的樣子擺放好。盤片在移動的過程中要遵守兩個規則：一次只能移動一個盤片;大盤片不能疊放在小盤片的上面。

講解完規則后，繼續借助于傳說，將學生的興趣和好奇心拉至最高點。如果按照這樣的規則進行搬移，梵天預言，一旦這些盤片完成搬移，世界將會毀滅。該結論一出，學生們紛紛表示懷疑;在這個互動環節，可以讓學生大致算一算，假如搬完所有盤片需要多長的時間？經過計算，搬完所有盤片需要移動的次數是264-1=1.8×1019次，也就是1800億億次，如果每秒搬動一次，則需要584，942，417，355年，也就是五千億年！拿五千億年和我們人類的長河幾百萬年相比，要搬完64個盤片是不可能的。

通過證實結論，學生的疑慮消除了，此時講解思路180度轉彎，視角回到當今的計算機時代、數據化時代，人工不能完成的事情是不是可以借助于計算機實現呢？借助于計算機，利用抽象化、自動化的方式將實際問題進行轉化，從而解決這個問題，這正是大學計算機基礎課程的目的，利用計算思維解決各領域的實際問題。

2 如何引導學生利用計算思維分析遞歸算法和漢諾塔之間的關系

計算思維是運用計算機科學的基礎概念進行問題求解、系統設計以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動。計算思維是運用計算機科學的基礎概念去求解問題、設計系統和理解人類的行為。它包括了涵蓋計算機科學之廣度的一系列思維活動。當我們必須求解一個特定的問題時，首先會問：解決這個問題有多么困難？怎樣才是最佳的解決方法？計算機科學根據堅實的理論基礎來準確地回答這些問題。表述問題的難度就是工具的基本能力，必須考慮的因素包括機器的指令系統、資源約束和操作環境[1，2]。

教師可以借助于提前準備好的教具-漢諾塔模型，讓學生以分組的方式動手嘗試簡單漢諾塔的移動過程，并展開小組討論。在實踐的過程中，有些小組成員思維反應較快，能夠完成5-6層漢諾塔的移動，有些小組陷入了移動的僵局。無論是完成快的小組還是慢的小組，都很難說清漢諾塔和遞歸算法之間的關系。

帶著這個問題，教師進行示范，從一個盤片的漢諾塔開始擺起，當擺到兩個盤片的漢諾塔時，學生思考總結出移動三部曲，先移走上面的小盤片至中間柱，再移動大盤片至右側的目標柱，最后移動小盤片到目標柱。利用移動三部曲，在挪動三個盤片的漢諾塔時，可以把上面的兩個小盤片看成一個整體，完成三部曲，再將整體還原為兩個小盤片，兩個小盤片的移動剛剛已經做過。這時，學生恍然大悟，可以利用三部曲嘗試移動3個甚至更多盤片。最后，教師進行總結，借助于五個盤片的漢諾塔，并用遞歸圖更好地詮釋了漢諾塔的三部曲移動正是借助了遞歸算法。

分析完漢諾塔和遞歸算法之間的關系后，整理思路，依據遞歸算法原理，設計求解漢諾塔問題的函數hanoi（n， A， B， C），設置4個參數，用n代表盤片的數量，用A、B、C分別代表起始柱、中間柱和目標柱。然后引導學生借助Python語言編寫該函數，利用IF、ELSE分支結構，分為兩種情況：當只有1個盤片時，直接從A柱移至B柱;當大于1個盤片時，按上述的移動三部曲進行移動。