遞迴的兩個層次

遞迴的兩個層次科學月刊【數‧生活與學習】專欄 9804 遞迴的兩個層次單維彰 98 年 3 月 7 日「遞迴」(recursion) 是一種思考的方法、解決問題的策略，也是一種表現數列規律性的形式，從這種形式可以用固定的代數程序換算成一般性的公式。高中數學課程自從 95 暫行綱要引進這個課題，但可能是因為缺乏詮釋也沒有範例，造成教學目標的不確定感，也形成評量上的疑慮。99 課綱對此課題有稍多的說明，並且限定在所謂的「一階遞迴」上，但有些教師還是認為不夠清晰明確。這一篇短文，企圖分兩個層次...

科學月刊【數‧生活與學習】專欄 9804 遞迴的兩個層次單維彰 98 年 3 月 7 日「遞迴」(recursion) 是一種思考的方法、解決問題的策略，也是一種表現數列規律性的形式，從這種形式可以用固定的代數程序換算成一般性的公式。高中數學課程自從 95 暫行綱要引進這個課題，但可能是因為缺乏詮釋也沒有範例，造成教學目標的不確定感，也形成評量上的疑慮。99 課綱對此課題有稍多的說明，並且限定在所謂的「一階遞迴」上，但有些教師還是認為不夠清晰明確。這一篇短文，企圖分兩個層次向一般讀者介紹「遞迴」，並順便嘗試以個人的理解來詮釋高中課程裡的遞迴課題。我要強調「個人」和「嘗試」兩個關鍵詞。第一個層次，視遞迴為數列規律性的一種形式。令 , , …是一個數列，意思就是「一系列的數」。數列不一定有規律，例如我們按照座號請學生報 1a , 2a 3a 出他生日中的日期部分，就會得到一個介於 1 和 31 之間的整數數列，卻不見得能觀察到什麼規律。但是有些數列是有規律的，而表現其規律性的形式之一，就是說每一項和它前一項之間的關係。例如，從 1 開始以 2 為公差的等差數列（其實就是奇數）1, 3, 5, …就有如此的遞迴關係： 11 a 且 21  nn aa ，從此以後 n 。得到 na 和 n 的關係。承接前一段的例子，因為都代表某個大於 1 的正整數。每一項只跟前一項有關的遞迴關係，稱為一階遞迴利用一階遞迴關係，有一種固定的代數程序，可以轉換成一般公式，也就是 … 把這些等式全部加起來，得到 11 a 2 2 21  aa 23  aa 21  nn aa )1(2...1... 121321   naaaaaaa nn 121 ...  naaa ，可以抵銷，因此很明顯地，等式的左右兩側都有 12)1(21  nnan 這就是所謂的一般項公式。上述的代數形式可以用來推導任意一階遞迴關係的一我們不該從少數幾項數列斷言它們的規律性。例如，看到 1, 4, 7, 10 這幾項，未必下一項就是 13。譬如，它們可能是一個函數的整數值：f(1)=1, f(2)=4, f(3)=7, f(4)=10，固然有可能般項公式。 23)(  xxf ，所以 f(5)=13，但是 f(x)也可能是 xxxxxxxxxxxf  )1()2)(1( 3 1)3)(2)(1( 12 1)( 那麼下一項其實是 f(5)=15。運用同樣的想法，其實可以創造無窮多種可能的 f(5)。所以，要發現有意義的數列規律性，不該單純地只看前面幾項的數，而是應該觀察某個具體程序所導致的數列。例如 97 年大學指定考試的數學甲科目，有一道題目以舉例說明的方式，定義每邊 1 顆、2 顆、3 顆和 4 顆球的正五邊形如下，而定義 1a , 2a , 3a , …是它們總共含有的球數。可見 11 a , 52 a , 123 a , …。若要用遞迴的策略寫出它們的規律性，我們發球，交點處的兩顆球重複了，所以多出來 10234 現每邊是每邊 3 顆球的正五邊形，再加上三個邊，每邊 4 顆4 顆球的正五邊形，  顆球。根據這個經驗，我 … 到一般項公們發現一般而言 1 2n31  anan 。然後我們列出以下等式： 1 a 22312  aa 23323  aa 231   naa nn 於是得式 2 32)1( 2 3221(3)1(2)...32(31 2 nnnnnnnnan  高中數學課程，應該僅止於發現數列的規律 )...3 n  中的遞迴主題性，並用以得到一般項公式。而所謂的規律性，如前面的指考題目，不是單純由數字推測，而是由具體情境中的某種程序產生。這個層次的遞迴概念，並不只是代數操作而已，也可以成為一種思考方法，並解決某種程度的問題。但是，我在第一段所提的，遞迴作為一種思考方法與解題策略的層次，稍微更高一點。專業人士的遞迴思考方式，並不在乎前幾項的特例如何產生。他們的思考模式差不多是，假設有一個黑盒子可以處理任意 nk  的狀況，如何利用這個黑盒子解決一般的那是 95 年指考數學甲的題目，如下。不透明箱內有編號分別為 1至 9的九個球，每次隨機取出一個，記錄其編號後放回箱內；以表示前 n 次取球的編號之總和為偶數的機率。已知存在常數 r, s n 狀況？最近的指考與學測題目當中，僅有一題接近了這個層次。 )(nP 使得 )()1( nsPrnP  對任意正整數 n 都成立，求 r 與 s。我們並不需要算出 )1(P , )2(P , )3(P 等特例，也並沒有將 )1( nP 和 )(nP 的關係視為數列的規律性，就直接以遞迴的思考方式解決這個問題。要理解的是，n+1 次取球編號之和為偶數的情況，可以分成前 n 次的和為取的球也是奇數，或者前 n+1 況。奇數而第次取的球也是偶數這兩種情 n+1 次 n 次的和為偶數而第如果 )(nP 表示前 n 次的和為偶數的機率，則 )(1 nP 就表示前 n 次的和為奇數的機率。第 +1 次取的球是偶數的機率是n 9 4 、是奇數的機率是 9 5 ，所以 )( 99 ))(1( 9 )( 9 )1( nPnPnPnP  1554 有了這條遞迴關係，再知道 9 4)1( P ，當然就能輕易得到的一般公式。以，負擔。業的人，以及計算機科學領域中演算法專業的人，將來會需要發展這種思考策略。因此，似乎不必讓全體高中生都學習這個課題。很多高中生都私下表示，老師如果不是事先知道排列組合問題的作法，也沒那麼厲害可以看起來很輕鬆的解題；不少高中老師也承認。如果將遞迴的思考策表現遞迴思考策略之威力的最佳範例，應屬河內塔問題。只可惜這個問題太 )(nP 指考的數學題目，特別是數學甲的考題，經常在考學生的數學創造力。所即使 95 年的高中畢業生，在校期間並沒有正式被教導遞迴思考策略，這一題也不算太過份。但是，就課程與評量理論而言，這個題目不太恰當。而高中數學課程，也可以不必觸及這個層次的遞迴概念。因為，如果課程涵蓋這個層次，則評量的考題可能會非常難以掌握，而變成學生過度的如此的思考方式，以及這種思考方式（目前所知）對應的問題，並不普遍，只有數學領域中離散數學專略納入高中課程，像這樣令年輕人不服氣的題目，可能又會更多了。有名了，曝光率太高，許多學生在正式學習遞迴策略之前，可能就讀過它的解法，而降低了作為教學範例的效果。

                    本文档为【遞迴的兩個層次】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

遞迴的兩個層次

你可能还喜欢