無法貼圖 ,自己到 /sjjg/NO00223.htm 看去吧
1、調用子程序的含義:
在過程和函數的學習中,我們知道調用子程序的壹般形式是:主程序調用子程序A,子程序A調用子程序B,如圖如示,這個過程實際上是:
@當主程序執行到調用子程序A語句時,系統保存壹些必要的現場數據,然後執行類似於BASIC語言的GOTO語句,跳轉到子程序A(為了說得簡單些,我這裏忽略了參數傳遞這個過程)。
@當子程序A執行到調用子程序B語句時,系統作法如上,跳轉到子程序B。
@子程序B執行完所有語句後,跳轉回子程序A調用子程序B語句的下壹條語句(我這又忽略了返回值處理)
@子程序A執行完後,跳轉回主程序調用子程序A語句的下壹條語句
@主程序執行到結束。
做個比較:我在吃飯(執行主程序)吃到壹半時,某人叫我(執行子程序A),話正說到壹半,電話又響了起來(執行子程序B),我只要先接完電話,再和某人把話說完,最後把飯吃完(我這飯吃得也夠累的了J)。
2、認識遞歸函數
我們在高中時都學過數學歸納法,例:
求 n!
我們可以把n!這麽定義
也就是說要求3!,我們必須先求出2!,要求2!,必須先求1!,要求1!,就必須先求0!,而0!=1,所以1!=0!*1=1,再進而求2!,3!。分別用函數表示,則如圖:
我們可以觀察到,除計算0!子程序外,其他的子程序基本相似,我們可以設計這麽壹個子程序:
int factorial(int i){
int res;
res=factorial(I-1)*i;
return res;
}
那麽當執行主程序語句s=factorial(3)時,就會執行factorial(3),但在執行factorial(3),又會調用factorial(2),這時大家要註意,factorial(3)和factorial(2)雖然是同壹個代碼段,但在內存中它的數據區是兩份!而執行factorial(2)時又會調用factorial(1),執行factorial(1)時又會調用factorial(0),每調用壹次factorial函數,它就會在內存中新增壹個數據區,那麽這些復制了多份的函數大家可以把它看成是多個不同名的函數來理解;
但我們這個函數有點問題,在執行factorial(0)時,它又會調用factorial(-1)。。。造成死循環,也就是說,在factorial函數中,我們要在適當的時候保證不再調用該函數,也就是不執行res=factorial(I-1)*i;這條調用語句。所以函數要改成:
int factorial(int i){
int res;
if (I>0) res=factorial(I-1)*i; else res=1;
return res;
}
那麽求3!的實際執行過程如圖所示:
3、如何考慮用遞歸的方法來解決問題
例:求s=1+2+3+4+5+6+……+n
本來這個問題我們過去常用循環累加的方法。而這裏如要用遞歸的方法,必須考慮兩點:
1) 能否把問題轉化成遞歸形式的描述;
2) 是否有遞歸結束的邊界條件。
設:函數s(n)=1+2+3+…+(n-1)+n
顯然遞歸的兩個條件都有了:
1) s(n) =s(n-1)+n
2) s(1)=1
所以源程序為:
int progression(int n){
int res;
if (n=1 )res=1 else res=progression(n-1)+n;
return res;
}
4、遞歸的應用
中序遍歷二叉樹
void inorder (BinTree T){
if (T){
inorder(T->lchild);
printf(“%c”,T->data);
inorder(T->rchild);
}
}
現假設樹如圖(為了講解方便,樹很簡單)
@執行第壹次調用inorder1,T指向頂結點,T不為空,所以第二次調用inorder2;
@T指向頂結點的左子樹結點也就是B,不為空,所以第三次調用inorder3;
@T指向B結點的左子樹結點,為空,所以什麽都不執行,返回inorder2;
@打印B結點的DATA域值“b”;
@第四次調用inorder4,去訪問B子樹的右結點
@T指向B結點的右子樹結點,為空,所以什麽都不執行,返回inorder2;
@返回inorder1;
@打印A結點的DATA域值“a”;
@第五次調用inorder5,去訪問A子樹的右結點;
@T指向A結點的右子樹結點,為空,所以什麽都不執行,返回inorder1;
@inorder1執行完畢,返回。