函式呼叫
- call-by-value
- call-bu-address(reference)
與函式呼叫有關的一個重要記憶體管理機制
- call stack 呼叫堆疊
遞迴
在一個語言中,函式除了可以呼叫其他函式外,也可以呼叫自己本身函式,此種方式稱之為遞迴。
- 沒有終止條件時,會無窮盡地呼叫下去
- 必須設一個終止條件(不再呼叫的條件)
- 可取代迴圈
- 有些問題用遞迴解程式寫起來比較精簡,但不容易理解。
- 費氏級數
- 路徑追蹤
- 迷宮問題
- 二元搜尋樹追蹤
- 河內塔
- ‧‧‧
範例:使用遞迴來達成迴圈
用遞迴印出1~10
#include <iostream>
#include "stdio.h"
using namespace std;
void m(int i)
{
if (i == 1) return;
m(i-1); //遞迴呼叫
cout << i << " ";
}
void main(){
m(10);
}
Q:若要印出10~1?
範例:算階乘
範例:算階乘
#include < stdio.h >
int fact(int n)
{
if ( n<=1 )
return 1;
return n*fact(n-1); // n!=n*(n-1)!
}
void main(void)
{
int n;
scanf("%d",&n);
printf("%d!=%d\n",n,fact(n));
}
範例:取指數
#include <stdio.h>
int exponent(int a, int x)
{
if (x == 0) {
return 1;
}
else {
return a * exponent(a, x - 1);
}
}
void main(void)
{
int i;
for (i = 0; i <= 10; i++) {
printf("%2d%5d\n", i, exponent(2, i));
}
}
範例:九九乘法表 - 迴圈解與遞迴解
#include <iostream>
#include <iomanip>
using namespace std;
/*
注意:下面遞迴用法,若是先遞回後印,則為遞增,若是先印後遞回,則為遞減
*/
void LoopJ1(int j, int i, int min){
if (j > min) LoopJ1(j-1, i, min);
cout << i << "*" << j << "=" << setw(2) << i*j<< " ";
}
void LoopI1(int i, int min){
if (i > min) LoopI1(i-1, min);
LoopJ1(9, i, min);
cout << endl;
}
void LoopJ2(int j, int i, int min){
cout << i << "*" << j << "=" << setw(2) << i*j<< " ";
if (j > min) LoopJ2(j-1, i, min);
}
void LoopI2(int i, int min){
LoopJ2(9, i, min);
cout << endl;
if (i > min) LoopI2(i-1, min);
}
void main(void){
cout << "迴圈遞增示範:"<< endl;
for (int i = 1; i <= 9; i++){
for (int j=1; j <= 9; j++){
cout << i << "*" << j << "=" << setw(2) << i*j<< " ";
}
cout << endl;
}
cout << "遞迴遞增示範:"<< endl;
LoopI1(9,1);
cout << "迴圈遞減示範:"<< endl;
for (int i = 9; i >= 1; i--){
for (int j=9; j >= 1; j--){
cout << i << "*" << j << "=" << setw(2) << i*j<< " ";
}
cout << endl;
}
cout << "遞迴遞減示範:"<< endl;
LoopI2(9,1);
system("pause");
}
練習
將下列進位轉換程式以遞迴方式改寫迴圈敘述。
void main(void){
char hex[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int num;
cout << "請輸入一數:" ; cin >> num;
int base;
cout << "請輸入進位數(2, 8, 16):" ; cin >> base;
int r;
int output[100];
int counter = 0;
while (num >= base) {
r = num % base; //取餘數
output[counter++] = r;
num = num / base;//取商數
}
output[counter] = num;
while (counter >= 0) cout << hex[ output[counter--] ];
system("pause");
}