# 遞迴函式

遞迴函式是直接 (或間接) 調用了自身的函式。
利用遞迴函式可以將一個規模較大的問題轉壞為規模較小的同類問題來求解。

# 計算一個非負整數的 n!

• 特徵：
  1. 定義中包含該函式本身（即遞歸公式)
  2. 必須有終止條件
• 調用過程包括：
  1. 遞推：將問題不斷分解為更小規模的新問題，逐漸從未知向已知方向推測。
  2. 回歸：是從已知的條件出發，按遞推的逆過程，逐個求職，最後到達遞推的開頭，解決原問題。

int f(int n)  {

	if(n==0) {

		return 1;

    } else {

		return n*f(n-1); // 直接遞歸調用

	}

}

# Hanoi 河內塔問題

有 A,B,C 三根柱子，在 A 柱子上有 n 個大小不同的金盤，大盤在下，小盤在上。
要將 A 柱子上的金盤移動到 C 柱子上，每次只能搬動一個金盤，搬動過程中可以藉助任何一根柱子暫時存放金盤，但必須滿足大盤在下，小盤在上的條件。
編程顯示盤子移動的過程。 n 由用戶輸入。

# 運作分析

• 如果只有一個盤子，只需一步，直接從 A 柱移動到 C 柱，用 A ➡️ C 表示；
• 如果有 2 個盤子，共需要移動 3 步:
  1. 把 A 柱上的小盤子移動到 B 柱；用 A ➡️ B 表示；
  2. 把 A 柱上的大盤子移動到 C 柱；用 A ➡️ C 表示；
  3. 把 B 柱上的小盤子移動到 C 柱；用 B ➡️ C 表示；
• 如果要將 A 柱上的 n 個盤子（n 值較大），移動到 C 柱上去，必須先把上面的 n-1 個盤子從 A 柱移動到 B 柱上暫存，按這種思路，就可以把 n 個盤子的移動過程分作三大步：
  1. 把 A 柱上面的 n-1 個盤子移動到 B 柱；
  2. 把 A 柱上剩下的一個盤子移動到 C 柱；
  3. 把 B 柱上面的 n-1 個盤子移動到 C 柱；
• 其中 n-1 個盤子的移動過程又可按同樣的方法分為三大步，這樣就把移動過程轉化為一個遞歸的過程，直到最後只剩下一個盤子，按照移動一個盤子的方法移動，遞歸結束。

# 運算描述

hanoi (n,A,B,C)
	如果 n=1, 則 :
		顯示 A--->C // 並將一個金盤直接從 A 移到 C 上
	否則
		hanoi (n-1,A,C,B) // 將 n-1 個金盤借助 C 從 A 移到 B 上
		顯示 A--->C 
		hanoi (n-1,B,A,C) // 將 n-1 個金盤借助 A 從 B 移到 C 上

# 程式碼實現

#include <iostream>

using namespace std;

int s=0; // 全域變數記錄總共的移動次數

// 函式 move 將一個盤子從 x 移到 y

void move(char x,char y)

{

	cout<<x<<"---->"<<y<<endl;

	s++; //s 計算移動的次數

}

//hanoi 函式

void hanoi(int n, char a, char b, char c)

{

	if(n==1) {

		move(a,c);

	} else {

		hanoi(n-1,a,c,b); // 借助 c 將 n-1 個盤子從 a 移到 b

		move(a,c); // 從 a 移到 c

		hanoi(n-1,b,a,c); // 借助 a 將 n-1 個盤子從 b 移到 c

	}

}

int main()

{

	int m;

	cout<<"請輸入盤子數：";

	cin>>m;

	cout<<"移動"<<m<<"個盤子的過程如下："<<endl;

	hanoi(m, 'A', 'B', 'C');

	cout<<"一共移動了"<<s<<"次。"<<endl;

	return 0;

}

# 內聯函式

程序通過一組函數實現是一種好的設計方法。但是函數調用涉及執行時間的開銷。
C++ 提供的內聯函數可以減少函數調用的開銷。

inline <函式值型態> <函式名>(<形式參數表>)

{

	函式體

}

對用戶來說，內聯函式的定義與調用與普通函式的使用方法是相似的。

作為編譯系統，它將程序中調用內聯函式的語句（或表達式）用內聯函數體中的代碼進行替換。這樣在執行時就避免了對內聯函式的調用，從而減少了因函式調用所增加的時間開銷，提高了程序運行的效率。

使用內聯函式可以節省運行時間，但卻增加了目標程序的長度。因此一般只將規模很小而使用頻繁的簡單函數聲明為內聯函式。

# 內聯函式的使用

計算$1^2+ 2^2+ 3^2+…+ 10^2$，將計算整數平方的功能定義為內聯函式

inline int square(int x)

{

	return x*x;

}

int main()

{

	int i,sum=0;

	for(i=1;i<=10;i++) {

		sum+=square(i);

	}

	cout<<"sum="<<sum<<endl;

}

# 函式重載

函式重載是指在一個程序中，可以定義多個具有相同函式名，不同參數列表的函式（至少參數的類型或參數個數或參數類型的順序不同）。這些的函式被稱為重載函式。
當調用一個重載函式時，編譯系統將通過檢查函式調用中的實參個數、類型和順序來選擇恰當的函式。
重載函式通常用於實現功能類似，而所處理的數據類型不同的問題。

# 形參個數相同，但類型不同

使用函數重載編寫求一個整數和一個雙精度數的絕對值的函式。

int Abs(int x)

{

	return x>=0?x:-x;

}

double Abs(double x)

{

	return x>=0?x:-x;

}

int main()

{

	int a=-3;

	double b=35.5;

	cout<<Abs(a)<<endl; // 3

	cout<<Abs(b)<<endl; // 35.5

	return 0;

}

# 形参類型相同，但個數不同

使用函式重載編寫求兩個、三個以及四個整數的和的函式

int add(int x,int y)

{

	int sum;

	sum=x+y;

	return sum;

}

int add(int x,int y,int z)

{

	int sum;

	sum=x+y+z ;

	return sum;

}

int add(int x,int y,int z,int t)

{

	int sum;

	sum=x+y+z+t;

	return sum;

}

int main()

{

	cout<<add(3,5)<<endl;// 8

	cout<<add(3,5,7)<<endl;// 15

	cout<<add(3,5,7,9)<<endl;// 24

	return 0;

}

# 變數的作用域

變數的作用域是指變數的使用範圍。
根據變數的使用範圍不同，C++ 中的變量被分為區域變數和全局變數

# 局部變數

在一個函數內或複合語句內定義的變量稱為局部變數（函式的形參也屬於局部變數）。
局部變數只允許在其定義的函數或複合語句中使用，離開所在的函式或複合語句後該局部變數將不能使用。

• 主函式中定義的變數，不能在其他函式中使用。

int f(int n)

{

	for(int i=1;i<=n;i++) {

		sum+=i; // 錯誤，變數 sum 為主函式中的局部變數

	}

	return sum;

}

int main()

{

	int sum=0;

	sum=f(10);

	cout<<sum<<endl;

	return 0;

}

• 複合語句中定義的變數，也只能在該複合語句中使用。

int main()

{

	int i=1,j=3;

	cout<<i<<" " ;

	i++;

	{

		int i=0;

		i+=j*2;

		cout<<i<<", "<<j<<", ";

	}

	cout<<i<<", "<<j<<endl;

	// 結果 1,6,3,2,3

}

• for 語句中控制變數的作用域

int main()

{

	int i=1,j=3;

	cout<<i<<" " ;

	i++;

	{

		int i=0;

		i+=j*2;

		cout<<i<<", "<<j<<", ";

	}

	cout<<i<<", "<<j<<endl;

	// 結果 1,6,3,2,3

}

編譯系統（如：DevC++、Codeblock），通常將循環語句中定義的變數作為局部變數處理，因此該變數在循環外是不能使用的。

# 全局變數

全局變數說明於所有函式之外，可以為所有函式共同使用。
全局變數可以在各個函式之間建立數據的傳輸通道。

# 作用域運算子 ::

int a=3,b=5;// 定義兩個全局變數

int max(int a,int b)

{

	return a>b?a:b;

}

int main()

{

	int a=8;

	cout<<max(::a,b)<<endl; // 結果為 5

}

# extern 宣告

全局變數的作用範圍是從定義點到整個源程序的結束。在定義點之前，如果其它函式要引用全局變數，可以在該函式中用 extern 對全局變數進行聲明。

F1()

{

	extern a,b; // 全局變數宣告

	<使用全局變數a,b>

}

int a=2,b=5; // 全局變數定義

# 優缺點

• 使用全局變數，可以增加函式間的直接聯繫，減少函式定義時的參數。
• 由於全局變數在整個程序運行中始終佔用內存，這樣，使用全局變數將降低程序的通用性、可靠性和移植性，這是全局變數的負面作用。

# 變數的存儲類型

不同的變數所分配的存儲區域也不同，這就是變數的存儲類型。

# 內存區域

C++ 程式運行時使用的內存區域

# 四個儲存類型

變數的存儲類型是變數在內存中存儲的方式，根據變數的存儲類型，可以知道變數的作用域和生存期。
4 個存儲類型，分別是 auto （自動類）， register （寄存器類）， static （靜態類）和 extern （外部類）。

在 c++ 中定義一個變量的完整形式是：

<儲存類型> <資料型態> <變數名>;

# 自動變數 - 用 auto 修飾

用 auto 修飾，默認的定義方式
如：定義一個變數 i

auto int i; 跟 int i; 是相同的。

# 寄存器變數 - 用 register 修飾

將盡可能存放在 CPU 的寄存器中，以提高程式效率。

# 靜態變數 - 用 static 修飾

• 靜態變數分配在全局數據區中，定義時系統將提供默認的初始值。
• 靜態變數在編譯時分配存儲空間，在整個程序執行結束後釋放存儲空間。所以，靜態變數具有全局生命期。
• 根據聲明的位置不同，靜態變數又分為靜態局部變數和靜態全局變數。
• 靜態局部變數是在 “塊” 中定義的靜態變數。它具有局部作用域，卻有全局生命期。在 “塊” 執行結束後，該靜態局部變數並不釋放（其值依舊存在），以便下次調用時可繼續使用。

# 外部變數 - 用 extern 修飾

如果在一個源文件中定義的全局變量要在其它源文件中使用，則在使用前應該用 extern 進行聲明，表示該全局變量不是在本文件中定義的。
例如：在 1.cpp 文件中定義全局變數
int Dimension=100;
如果在 2.cpp 文件中使用，這時，應在 2.cpp 文件中聲明
如下：
extern int Dimension;