函式呼叫

• 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");
}