C語言中遞歸函數(shù)的設計

C語言中遞歸函數(shù)的設計主講人熊立偉（武漢大學遙感信息工程學院）1、教學目標使學生學會使用和設計遞歸函數(shù)去解決較復雜的問題2、教學重點遞歸函數(shù)的定義、遞歸問題的分類、遞歸函數(shù)設計的一般步驟3、教學難點理解遞歸函數(shù)的內涵、確定遞歸結束條件4、教學方法講故事激發(fā)學生興趣，巧解概念，典型例題分析

新課導入：C程序結構是函數(shù)模塊結構，C程序是由一個或多個函數(shù)構成的，是函數(shù)的集合。函數(shù)具有相對獨立的特定功能，是程序的基本單位，因此，在C語言教學中，函數(shù)這一章(大部分教材把函數(shù)作為一章)是重點內容，而函數(shù)的遞歸調用則是這一章的重點之一。下面我們首先來看遞歸函數(shù)的定義一、遞歸的定義

在調用一個函數(shù)的過程中調用該函數(shù)本身，稱為函數(shù)的遞歸調用。遞歸調用簡稱遞歸。

有這么一個古老的故事：從前有座山，山上有個廟，廟里有個老和尚和小和尚，老和尚給小和尚講故事，講的是:從前有座山，山上有個廟，廟里有個老和尚和小和尚，老和尚給小和尚講故事，講的是……

這是一個典型的“遞歸”故事，可以無限次遞歸下去。當大人們肚中無故事而又要哄小孩時，常常講這個故事。我們可把這個故事比喻成遞歸調用，但在C語言程序設計中，程序不可無限地遞歸下去，必須有遞歸結束條件，而且每次遞歸都應該向結束條件邁進，直到滿足結束條件而停止遞歸調用。為此，可將上述“遞歸”故事修改如下：

從前有座山，山上有個廟，廟里有個老和尚和3歲的小和尚，老和尚給小和尚講故事，講的是：從前有座山，山上有個廟，廟里有個老和尚和2歲的小和尚，老和尚給小和尚講故事，講得是：從前有座山，山上有個廟，廟里有個老和尚和1歲的小和尚。這里的遞歸結束條件即小和尚的年齡，因為沒有0歲的小和尚，所以講到“廟里有個老和尚和l歲的小和尚”時，故事結束。每次遞歸都使小和尚的年齡減少一歲，所以總有終止遞歸的時候，不會產(chǎn)生無限遞歸。二、遞歸的分類1、數(shù)值問題可以表達為數(shù)學公式的問題，如求非負整數(shù)N的階乘、求斐波那契數(shù)列的第n項、求兩個整數(shù)的最大公約數(shù)等。2、非數(shù)值問題其本身難以用數(shù)學公式表達的問題，如著名的漢諾塔問題、八皇后問題。三、遞歸函數(shù)設計的一般步驟編寫遞歸程序有兩個要點：一是要找到正確的遞歸算法，這是編寫遞歸程序的基礎；二是要確定遞歸算法的結束條件，這是決定遞歸程序能否正常結束的關鍵。

前面我們把遞歸問題分為兩大類：數(shù)值問題和非數(shù)值問題。這兩類問題具有不同的性質，所以解決問題的方法也不同。

對于數(shù)值問題，由于可以表達為數(shù)學公式，所以可以從數(shù)學公式入手推導出問題的遞歸定義，然后確定問題的邊界條件，從而確定遞歸的算法和遞歸結束條件。

對于非數(shù)值問題，其本身難以用數(shù)學公式表達。求解非數(shù)值問題的一般方法是要設計一種算法，找到解決問題的一系列操作步驟。如果能夠找到解決問題的一系列遞歸操作步驟，同樣可以用遞歸的方法解決這些非數(shù)值問題，尋找非數(shù)值問題的遞歸算法可以從分析問題本身的規(guī)律入手，可以按照下列步驟進行分析：第一步，將問題進行化簡，將問題的規(guī)?？s到最小，分析問題在最簡單情況下的求解方法，這時的算法應當是最簡單的非遞歸算法。

第二步，將問題分解為若干個小問題，其中至少有一個小問題具有與原問題相同的性質，只是在規(guī)模上比原問題有所縮小，將分解后的每個小問題作為一個整體，描述用這些較小的問題解決原來較大問題的算法。由第二步得到的算法就是一個解決原問題的遞歸算法，第一步將問題的規(guī)?？s到最小時的條件就是該遞歸算法的結束條件。三、典型例題分析首先來看一個數(shù)值問題的遞歸算法例1用輾轉相除法求整數(shù)m與n的最大公約數(shù)。討論：此問題屬于數(shù)值問題，求m與n的最大公約數(shù)等價于求n與(m%n)的最大公約數(shù)，這時可以把n當作新的m,(m%n)當作新的n，問題變成了求新的m與新的n的最大公約數(shù)，它又等價于求新的n與(m%n)的最大公約數(shù)……如此繼續(xù)，直到新的n=0時，所求最大公約數(shù)就是新的m，這就是用輾轉相除法求m與n的最大公約數(shù)的過程。因此，有如下遞歸算法：

1.求r=m%n2.若r=0，則n為所求，輸出n，結束

3.若r!=0，則令m=n,n=r4.轉向步驟1

按照上述算法可編寫出如下C語言程序：

#include<stdio.h>voidmain(){

int

gcd(int

m,intn);

int

m,n,g;

printf(“請輸入整數(shù)m,n:”);

scanf(“%d%d”,&m,&n);

printf(“\n”);

g=gcd(m,n);

printf(“%d和%d的最大公約數(shù)是：%d\n”,m,n,g);}

int

gcd(int

m,intn){

intg;if(n==0)

g=m;else

g=gcd(n,m%n);returng;}下面我們再來看一個非數(shù)值問題的遞歸算法例2漢諾塔(Hanoit)問題這是一個著名的問題，相傳在很久很久以前，在中東地區(qū)的一個寺廟里，幾個和尚整天不停地移動著盤子，日復一日，年復一年，移盤不止，移動盤子的規(guī)則是這樣的：事先固定三根針，假設分別為A針、B針、C針，A針上套有64個中間帶孔的盤子，盤子大小不等，大的在下，小的在上，要求把這64個盤子從A針移到C針，在移動過程中可以借助于B針，每次只允許移動一個盤子，且移動過程中的每一步都必須保證在三根針上都是大盤在下、小盤在上。據(jù)說當所有64個盤子全部移完的那一天就是世界的末日，故漢諾塔問題又被稱為“世界末日問題”。不難計算，對于n個盤子需要移動2n-1次，把64個盤子都移動完畢約需1.8X1019次，假設每秒移動一次，約需一萬億年，若用現(xiàn)代電子計算機計算，設一微秒可計算(并不輸出)一次移動，也幾乎需要一百萬年。目前，由于計算機運算速度的限制，我們僅能找出問題的解決方法并解決較小n值的漢諾塔問題。討論：漢諾塔問題屬于非數(shù)值問題，難以用數(shù)學公式表達其算法，可以從分析問題本身的規(guī)律入手。第一步，問題化簡，設A針上只有一個盤子，即n=1，則只需將1號盤從A針移到C針。第二步，問題分解，對于有n（n>1）個盤子的漢諾塔，可分為三個步驟求解：

1.將A針上n-1個盤子借助于C針移到B針

2.把A針上剩下的一個盤子移到C針

3.將B針上n-1個盤子借助于A針移到C針顯然，上述1,3兩步具有與原問題相同的性質，只是在問題的規(guī)模上比原問題有所縮小，可用遞歸實現(xiàn)。整理上述分析結果，把第一步作為遞歸結束條件，將第二步分析得到的算法作為遞歸算法，可以寫出如下完整的遞歸算法描述：定義一個函數(shù)movedisk(int

n,char

fromneedle,chartempneedle,chartoneedle)，該函數(shù)的功能是將fromneedle針上的n個盤子借助于tempneedle針移動到toneedlee針，這樣移動n個盤子的遞歸算法描述如下：

movedisk(int

n,char

fromneedle,char

tempneedle,char

toneedle){if(n==1)將n號盤子從one針移到three針;

esle1.movedisk(n-1,fromneedle,toneedle,

tempneedle)

2.將n號盤子從fromneedle針移到toneedle針;3.movedisk(n-1,tempneedle,fromneedle,

toneedle)}

按照上述算法可編寫出如下C語言程序：

#include<stdio.h>voidmain(){voidmovedisk(int

n,char

fromneedle,char

tempneedle,char

toneedle);

intn;

printf(“Pleasesinputthenumberofdiskes:”);

scanf(“%d”,&n);

printf(“Thestepmovingdiskes

is:\n”);

movedisk(n,’A’,’B’,’C’);}voidmovedisk(int

n,char

fromneedle,char

tempneedle,char

toneedle){if(n==1)printf(“%c

%c\n”,fromneedle,toneedle);else{

movedisk(n-1,fromneedle,toneedle,tempneedle);

printf(“%c

%c\n”,fromneedle,toneedle);

movedisk