一、函數的參數

1.形式參數和實際參數

1.1形式參數

形參出現在被調函數當中，在整個函數體內都可以使用。形參在定義時編譯系統并不分配存儲空間，只有在調用該函數時才分配內存單元。調用結束內存單元被釋放，故形參只有在函數調用時有效，調用結束時不能再使用。

1.2實際參數

實參出現在主調函數當中，當函數調用時，朱調函數把實參的值傳送給被調函數的形參，從而實現函數間的數據傳遞。傳遞方式有兩種：值傳遞和地址傳遞方式。

2.變量作為函數參數

當形參定義為變量時，實參可以是常量、變量和表達式，這種函數間的參數傳遞為值傳遞方式。值傳遞的特點是參數的“單向傳遞”；

int swap(int a,int b) {int temp;temp=a;a=b;b=temp;return 0; } int main (void){int a=3,b=4;swap(a,b);}

由于是值傳遞，單向傳遞，并不會改變a，b的值。

3.數組作為函數參數

3.1數組元素作為函數參數

數組元素又稱為下標變量，它具有普通變量的一切性質，因此數組元素作為函數的實參進行數據傳遞是與普通變量沒有任何區別，也是值傳遞

int swap(int a,int b) {int temp;temp=a;a=b;b=temp;return 0; } int main (void){int a[]={3,4};swap(a[0],b[0]);}

同樣是值傳遞并不會改變a[0]的值。

3.2一維數組名作為函數參數

數組名是一個地址，是數組的首地址，因此用數組名作為函數的參數進行數據傳遞時，執行的是地址傳遞方式。所謂地址傳遞，顧名思義實參傳遞的不是數據本身，而是數據存在的地址。函數調用時，把數組名即數組的首地址作為實參傳遞給形參（必須是可接受地址的數組名或者指針變量），形參數組名取得首地址后就有了實在的數組，這時實質上實參和形參是同一個數組，指向同一段存儲空間，實參的改變就是對形參的改變，所以傳址方式可看成是數據進行了“雙向傳遞”。

3.3數組指針，即數組元素的地址作為函數參數

由于數組元素的地址的本質仍然為地址，所以屬于地址傳遞方式。

int swap(int *a,int *b) {int temp;temp=*a;*a=*b;*b=temp;return 0; } int main (void){int arr[] = {1,2};int *a = &arr[0];int *b = &arr[1];swap(a,b);}

重點：

• 數組元素（下標變量）作為函數的參數進行的數據傳遞是值傳遞方式，數組名（數組首地址）、數組元素的地址（&arr[0]）作為函數參數進行的數據傳遞是地址傳遞方式。
• 實參為數組名是，形參接收時可以有三種形式：帶下標的數組名(arr[0])。不帶下標的數組名（arr）、可接收地址值的指針變量名（*a）。由于是參數組和形參數組都指向同一段內存單元，故它們操作的是同一批數據，所以形參的改變就是改變了實參中的數據。

局部變量

是什么？首先是一個變量，其次，這個變量只是在程序的局部范圍內有效；
局部變量定義在那些位置：
1. 函數的開頭；
2. 函數內的復合語句內定義；
3. 形式參數；
4. 函數中間（非開頭）；

#include <stdio.h> void main() { } void fun1(char local_0) //形式參數：只在此函數有效； {char Local_1 = 'a'; //函數的開頭：在本句以下的函數內有效；{char local_2 = 'b'; //函數的復合語句內定義：只能在本復合語句內切本行以下有效；}char Local_3 = 'c'; //函數中間(非開頭)：只能在本行以下有效； }

注意：
1）程序執行到某個函數時，這個函數內部的局部變量將會被分配內存空間；局部變量在函數執行結束后，變量所占內存將會被釋放；

全局變量

是什么？是變量，可以在全局范圍內有意義的變量；所謂全局也并不是真正的全局，而是在定義處以下的范圍內才是有效的；
全局變量定義的位置:
1. 文件開頭；
2. 函數前；
3. 函數后；
4. 文件結尾；
舉例：

#include <stdio.h>char Global_1 = 'A'; //源文件開頭：在此行以下的所有定義的函數都有效； void main() { }char Global_2='B'; //函數后和函數前：此全局變量在此行之前是無效，只能在此之下的函數中有效；void fun1() {char Local_1 = 'a';{char local_2 = 'b';}char Local_3 = 'c'; }char Global_3 = 'B';//程序結尾：程序結尾的全局變量是沒有意義的；

注意：
1）為了區別全局變量和局部變量，往往大家在寫程序的時候都喜歡將全局變量的首字母大寫，而局部變量的首字母小寫；
2）全局變量的優點和缺點：
優點：C語言的函數，每次最多只能返回一個值，但是如果定義了全局變量，那么在這個變量的有效范圍內，很多函數都能改變這個變量的值，所以增加了函數之間的聯系，通過函數的調用可以得到一個或一個以上的值；
缺點：（大量使用全局變量的情況下）
1）占內存：全局變量所占的內存空間不會像局部變量一樣會被釋放；
2）降低程序清晰性：無法隨時確定定義的全局變量的值的大小；
3）降低通用性：程序設計時要求函數的“內聚性”強，函數與函數之間“耦合性”弱；定義全局變是一定要注意在有效范圍內變量不能重名，并且當全局變量被跨文件調用的函數調用時，不能出現全局變量與所跨文件中存在重名變量，否則有可能會出錯；所以，為了提高程序的可靠性，可移植性和可讀性等，全局變量盡量少用；

二、函數的返回

函數的返回值是指函數被調用之后，執行函數體中的代碼所得到的結果，這個結果通過 return 語句返回。
return 語句的一般形式為：

return 表達式;

或者：

return (表達式);

有沒有( )都是正確的，為了簡明，一般也不寫( )。例如：

return max; return a+b; return (100+200);

對C語言返回值的說明：

沒有返回值的函數為空類型，用void表示。例如：

void func(){printf("http://c.biancheng.net\n"); }

一旦函數的返回值類型被定義為 void，就不能再接收它的值了。例如，下面的語句是錯誤的：

int a = func();

為了使程序有良好的可讀性并減少出錯， 凡不要求返回值的函數都應定義為 void 類型。

return 語句可以有多個，可以出現在函數體的任意位置，但是每次調用函數只能有一個 return 語句被執行，所以只有一個返回值（少數的編程語言支持多個返回值，例如Go語言）。例如：

//返回兩個整數中較大的一個 int max(int a, int b){if(a > b){return a;}else{return b;} }

如果a>b成立，就執行return a，return b不會執行；如果不成立，就執行return b，return a不會執行。

函數一旦遇到 return 語句就立即返回，后面的所有語句都不會被執行到了。從這個角度看，return 語句還有強制結束函數執行的作用。例如：

//返回兩個整數中較大的一個 int max(int a, int b){return (a>b) ? a : b;printf("Function is performed\n"); }

第 4 行代碼就是多余的，永遠沒有執行的機會。
下面我們定義了一個判斷素數的函數，這個例子更加實用：

#include <stdio.h>int prime(int n){int is_prime = 1, i;//n一旦小于0就不符合條件，就沒必要執行后面的代碼了，所以提前結束函數if(n < 0){ return -1; }for(i=2; i<n; i++){if(n % i == 0){is_prime = 0;break;}}return is_prime; }int main(){int num, is_prime;scanf("%d", &num);is_prime = prime(num);if(is_prime < 0){printf("%d is a illegal number.\n", num);}else if(is_prime > 0){printf("%d is a prime number.\n", num);}else{printf("%d is not a prime number.\n", num);}return 0; }

prime() 是一個用來求素數的函數。素數是自然數，它的值大于等于零，一旦傳遞給 prime() 的值小于零就沒有意義了，就無法判斷是否是素數了，所以一旦檢測到參數 n 的值小于 0，就使用 return 語句提前結束函數。

return 語句是提前結束函數的唯一辦法。return 后面可以跟一份數據，表示將這份數據返回到函數外面；return 后面也可以不跟任何數據，表示什么也不返回，僅僅用來結束函數。

更改上面的代碼，使得 return 后面不跟任何數據：

#include <stdio.h>void prime(int n){int is_prime = 1, i;if(n < 0){printf("%d is a illegal number.\n", n);return; //return后面不帶任何數據}for(i=2; i<n; i++){if(n % i == 0){is_prime = 0;break;}}if(is_prime > 0){printf("%d is a prime number.\n", n);}else{printf("%d is not a prime number.\n", n);} }int main(){int num;scanf("%d", &num);prime(num);return 0; }

prime() 的返回值是 void，return 后面不能帶任何數據，直接寫分號即可。

三、函數的調用

一，函數的定義

一般來說，執行源程序就是執行主函數main，其他函數只能被主函數所調用，而其他函數之間也可以相互調用。

1.標準庫函數：

分為：I/O函數，字符串，字符處理函數，數學函數，接口函數，時間轉換和操作函數，動態地址分配函數，目錄函數，過程控制函數，字符屏幕和圖形功能函數。

這些庫函數在不同的頭文件中聲明。比如：

math.h頭文件中有：sin(x),cos(x),exp(x)（求e^x），fabs(x)（求x的絕對值）等庫函數。

stdio.h頭文件中有：scanf(),printf(),gets(),puts(),getchar(),putchar()等庫函數。

string.h頭文件中有：strcmp(),strcpy(),strcat(),strlen等庫函數。

2.函數的定義：

（1）定義無參函數：

類型名? 函數名（）

{

函數體

}

or

類型名? 函數名（void）

{

函數體

}

（2）定義有參函數

類型名 函數名（形式參數表列）

{

函數體

}

（3）定義空函數

類型名 函數名（）

{? ? }

二，函數的調用

1.函數調用時的參數傳遞

函數間通過參數來傳遞數據，即通過主調函數中的實際參數（實參）向被調用函數中的形式參數（形參）進行傳遞。

實參向形參傳遞數據的方式：實參將值單向傳遞給形參，形參的變化不影響實參值。

for example:

#include<stdio.h> #include<stdlib.h> int main() {int a, b;void swap(int a, int b); //函數聲明scanf("%d%d", &a, &b); //鍵盤輸入swap(a, b); //函數調用printf("最終的a,b值:\n a=%d b=%d\n", a, b);system("pause");return 0; } void swap(int a, int b) {int t;if (a < b){t = a;a = b;b = t; //a中放大值，b中放小值}printf("自定義函數的a,b值：\n a=%d b=%d\n", a, b); }

運行結果為：

分析：形參交換了數據，而實參保持原數據不變。這是單向的值傳遞，所以形參的值改變后而實參的值沒有改變。

• 形參在函數中是變量名，在函數調用時，形參被臨時分配相應的內存，調用結束后，形參單元被釋放，而實參單元保留并維持原值。
• 實參是表達式，負責向對應的形參標識的內存單元傳遞數據，實參向形參的數據傳遞是“值傳遞”。
• 實參與形參必須個數相同
• 對應的形參和實參的類型必須一致

2.函數的返回值

（1）函數的返回值通過函數中的return語句獲得。如果需要從調用函數帶回一個函數值（供主函數使用），被調函數中需包含return語句。

for example:

int max(int x,int y) {return(x>y?x:y); }

(2)在定義函數時要指定函數值的類型

int max(float x,float y) //函數值為整型 char letter(char c1,char c2) //函數值為字符型 double max(int x,int y) //函數值為雙精度型

（3）函數類型決定返回值的類型。

3.函數的嵌套

定義函數時不能定義另一個函數，但是可以進行嵌套調用函數。

for example:

*用函數嵌套找出4個數中的最大值。

#include<stdio.h> #include<stdlib.h> int max2(int a, int b) //找出a和b中的最大值 {if (a >= b){return a; // a作為返回值}return b; // b作為返回值 } int max4(int a, int b, int c, int d) //定義找4個數最大值的函數 {int m; //存最大值m = max2(a, b); //調用max2函數，將a,b中大的值放在m中m = max2(m, c); //調用max2函數，將a,b，c中大的值放在m中m = max2(m, d); //調用max2函數，將a,b,c,d中大的值放在m中return m; //返回到主函數 } int main() {int a, b, c, d;int max;printf("請輸入四個數：\n");scanf("%d%d%d%d", &a, &b, &c, &d);max = max4(a, b, c, d); //調用max4函數printf("最大數位：%d\n", max);system("pause");return 0; }

三，函數的遞歸

1.遞歸概念：

函數的遞歸調用是指：一個函數在他的函數體內直接或間接地調用它自身。分為：直接遞歸（函數直接調用自身）和間接遞歸（函數通過其他函數調用自身）。可分為“回溯”和“遞推”兩個階段。

2.遞歸函數的一般形式：

反值類型? ?遞歸函數名（參數說明表）

{

if(遞歸終止條件)

返回值=遞歸終止值；

else

返回值=遞歸調用（...）的表達式；

return 返回值；

}

3.遞歸函數舉例：

*用遞歸求n的階乘。

#include<stdio.h> #include<stdlib.h> int fac(int n) //定義函數 {int f;if (n < 0)printf("數據錯誤\n");else if (n == 0 || n == 1)f = 1;elsef = n* fac(n - 1); //n!=n*(n-1)return f; //返回主函數 } int main() {int n, y;printf("請輸入n的值\n");scanf("%d", &n);y = fac(n); //這里n為實參printf("%d!=%d\n", n, y);system("pause");return 0; }

漢諾塔問題為經典的遞歸調用實例。代碼如下：

#include<stdio.h> #include<stdlib.h> void move(char x, char y) //輸出移盤方案 {printf("%c->%c\n", x, y); } void hanoi(int n, char one, char two, char three) //移盤 {if (n == 1)move(one, three); //如果是1個盤，直接從第一個座移到第3個座上else{hanoi(n - 1, one, three, two); move(one, three);hanoi(n - 1, two, one, three);} } int main() {int n;printf("輸入盤的個數\n");scanf("%d", &n);printf("移盤的步驟：\n");hanoi(n, 'A', 'B', 'C');system("pause");return 0;

分析：將n個盤子從A座上移到C座上需要三步：

（1）將A上的n-1個盤子借助C座先移到B座上；

（2）把A座上剩下的一個盤子移到C座上；

（3）將n-1個盤從B座上借助于A移到C座上。

函數的調用，一般是對同一個源文件中的其他函數進行調用的，也可以對另外一個源文件中的函數進行調用
C語言中，根據函數能否被其他源文件調用，分為內部函數和外部函數
外部函數，可以被其他源文件調用的函數
內部函數，只在定義的文件中有效

外部函數

開發大型項目，可能包含很多源文件來分別實現，最終，再整合在一起，有時，一個源文件中，需要調用其他源文件中的函數
調用外部函數之前，需要在當前源文件中定義外部函數
定義外部函數的方式，在函數的返回值類型前面添加extern關鍵字
示例代碼
extern int add(int x,int y);
編譯器，通過extern關鍵字會知道，add()函數是定義在其他文件中的外部函數
示例代碼

第一個源文件 int add(int x,int y) { return x+y; } 第二個源文件 #include <stdio.h> extern int add(int x,int y); void main() { printf("sum=%d\n",add(1,2)); }

運行結果

C語言中
定義外部函數時，可以省略關鍵字extern
修改如下
int add(int x,int y);

由函數的返回類型、函數名和參數列表組成，這類格式的代碼被稱為函數原型
當代碼中包含函數原型時，可能有兩種情況
1、程序員希望編譯器自動從其他文件中，查找該函數的定義
2、程序員先定義未實現的空函數，然后，在其他文件中具體實現

注意
聲明外部函數時，無論有沒有關鍵字extern，外部函數與原函數定義的返回值類型、函數名稱和參數列表必須一致

內部函數

外部函數，只要聲明一個函數原型，就可以調用其他源文件中的函數，但是，當多人開發時，可能出現函數重名的情況，不同源文件中的同名函數會相互干擾
此時，就需要一些特殊函數，只在定義的文件中有效，這類函數稱為內部函數

定義內部函數
在定義內部函數時，需要在函數的返回值類型前面添加static關鍵字，也稱靜態函數
示例代碼

第一個文件 #include<stdio.h> void show() { printf("%s \n","first.c"); } 第二個文件 #include<stdio.h> static void show() { printf("%s \n","second.c"); } void main() { show(); }

運行結果

如果，將第二個文件中的static去
運行程序會報錯

四、函數的遞歸

函數遞歸的定義和優缺點

程序調用自身的行為就是遞歸。可以直接或間接的調用，本質是把復雜的問題轉化為一個規模小的問題。遞歸一般只需少量的代碼就可描繪出多次重復計算。其主要思考方式在于大事化小。

優點是為具有某些特征的編程問題提供了最簡單的策略，缺點是層層調用，算法的復雜度可能過高，以致于快速耗干了計算機的內存資源，不方便閱讀和維護等。

遞歸的使用場景及必要條件

使用場景

能夠要求轉化為新的問題，且二者解決方法相同，所處理的對象存在規律變化。

非遞歸比較麻煩，而遞歸很簡單。

有模板或是公式可以直接套用，不會出現明顯問題。

必要條件

• 明確存在限制條件
• 每次遞歸越來越逼近條件

遞歸的細節說明

• 每級遞歸都有自己的變量，可能名稱相同，但是其值不同。

  遞歸調用時，系統自動保留當前函數的參數變量。每次調用系統都會為函數開辟相應的空間。

• 每次調用都要返回值，遞歸執行結束后，控制權傳回到上一級函數。

  調用結束后，系統釋放本次調用所開辟的空間，程序返回到上一次的調用點，同時獲得初進該級調用的參數。

  每級遞歸必須逐級返回，不可跳躍或間斷。

• 函數中遞歸語句之前的代碼，按被調函數的順序執行，遞歸之后的代碼，與被調函數相反的順序執行。

遞歸的習題講解

1打印整數每一位

用遞歸的方式，實現打印一個整數的每一位的功能。

輸入輸出示例

輸入：1234

輸出：1 2 3 4

解題思路

print(1234)
= =?=?print(123)+4
= =?=?print(12)+3+4
= =?=?print(1)+2+3+4
= =?=?printf(1)+2+3+4

這便是前面使用場景中所寫的，將題目要求問題轉化為新的問題，且變量有規律的變化

代碼邏輯

n是不是個位數，遞推調用n / 10

n是個位數，回歸打印n % 10

void Print(int n) {if (n > 9){Print(n / 10);}printf("%d ", n%10); } int main() {int num = 0;scanf("%d", &num);Print(num); return 0; }

2遞歸和非遞歸求n階乘

用遞歸和非遞歸的方法，分別實現求n的階乘的功能（不考慮溢出）。

輸入輸出示例

輸入：5

輸出：120

解題思路

n ? n ? 1 ? n ? 2 ? n ? 3 ? … ? 1 n*n-1*n-2*n-3*…*1?n?n?1?n?2?n?3?…?1

代碼邏輯

f a c ( n ) = n ? f a c ( n ? 1 ) , n > 0 fac(n) = n * fac(n-1) , n>0?fac(n)=n?fac(n?1),n>0

f a c ( n ) = 1 , n = 0 fac(n) = 1 , n=0?fac(n)=1,n=0

int fac(int n)//非遞歸 {int ret = 1;for (int i = 1; i <= n; i++){ret *= i;}return ret; } int fac(int n)//遞歸 {if (n > 0)return n * fac2(n - 1);elsereturn 1; } int main() {int n = 0;scanf("%d", &n); printf("%d\n", fac(n));return 0; }

3strlen函數模擬

輸入輸出示例

輸入：abcdef

輸出：6

解題思路

strlen(abcdef\0)
1+strlen(bcdef\0)
1+1+strlen(cdef\0)
1+1+1+strlen(def\0)
1+1+1+1+strlen(ef\0)
1+1+1+1+1+strlen(f\0)
1+1+1+1+1+1+strlen(\0)

代碼邏輯

若 ? c h ≠ 0 , s t r l e n ( a r r ) = 1 + s t r l e n ( a r r + 1 ) 若 *ch≠0 , strlen(arr) = 1 + strlen(arr+1)?若?ch?=0,strlen(arr)=1+strlen(arr+1)
若 ? c h = 0 , s t r l e n ( a r r ) = 0 若*ch=0 , strlen(arr) = 0?若?ch=0,strlen(arr)=0

int my_strlen(char* ch) {if (*ch != '\0'){return 1 + my_strlen(ch + 1);}return 0; } int main() {char ch[20] = { 0 };scanf("%s", &ch);printf("%d", my_strlen(ch));return 0; }

4逆序字符串

不開辟額外空間的情況下，不使用字符串庫函數，遞歸實現字符串反向排列，而不是倒序打印。

輸入輸出示例

輸入：abcdef

輸出：fedcba

解題思路

abcdef

遞推：（先把后面賦值給前面，后面用覆蓋\0）

$ \Rightarrow$?f b c d e \0

? \Rightarrow???f e c \0\0

? \Rightarrow???f e d \0\0\0

回歸：（把前面轉移出去的字符對應賦值給\0）

$ \Rightarrow$?f e d c \0\0

? \Rightarrow???f e d c b \0

? \Rightarrow???f e d c b a

代碼邏輯

reverse("abcdef\0") 交換a和f+reverse("f bcde\0\0") 交換a和f+交換b和e+reverse("fe cd\0\0\0") 交換a和f+交換b和e+交換c和d+reverse("fed \0\0\0\0")

• 交換兩個字符
• 將在前的字符先放到一邊存著
• 把在后的字符賦值到前面的位置
• 再把后面的位置對應覆蓋為\0
• 原在前字符替換\0
• 把事先存好的在前的字符對應替換到\0的位置上

void reserve_string1(char* ch)//指針 {char* left = ch;char* right = ch + strlen(ch) - 1;while (left < right){char tmp = *left;//不能交換地址，只能交換內容*left = *right;*right = tmp;left++;right--;} } void reserve_string2(char* ch)//數組 {int left = 0;int right = strlen(ch) - 1;while (left < right){char tmp = ch[right];ch[right] = ch[left];ch[left] = tmp;left++;right--;} }void reverse_string3(char* ch)//遞歸 {char* left = ch;char* right = ch + strlen(ch) - 1;if (*ch != '\0'){char tmp = *left;//提取*left = *right;//賦值*right = '\0';//賦\0reverse_string3(ch+1);//ch+1,而不是ch++*right = tmp;//賦值} } int main() {char ch[20] = "abcdef";//char* ch = "abcdef";//err - 常量字符串不可修改reverse_string3(ch);printf("%s\n", ch);return 0; }

5遞歸實現數字各位之和

寫一個遞歸函數DigitSum()，輸入一個非負整數，返回組成它的數字之和

輸入輸出示例

輸入：1234

輸出：10

解題思路

1234
DigitSum(123)+4
DigitSum(12)+3+4
DigitSum(1)+2+3+4

1+2+3+4

1234%10=4
1234/10=123

123%10=3
123/10=12

12%10=2
12/10=1

1%10=1
1/10=0

一個數模10得到尾數，除10得到尾數前面的數字

通過不斷的除10模10，就可以把每一位數字放到末尾，從而得到每一位數字

代碼邏輯

若n不為個位數，先%10得到尾數，再/10

一定要有遞歸的出口，即當n為個位數時，函數返回n

int DigitSum(int n) {if (n > 9)return DigitSum(n / 10) + n % 10;elsereturn n;//遞歸的出口 } int main() {int n = 0;scanf("%d", &n);printf("%d\n", DigitSum(n));return 0; }

6求n的k次冪

輸入兩個整數分別代表底數和次冪，遞歸實現n的k次冪的功能。

輸入輸出示例

輸入：2 3

輸出：8

解題思路

當k>0時，函數返回n*power(n,k-1)

當k=0時，函數返回1，這是程序的出口，是程序遞歸到最后必須要計算的值

代碼邏輯

n k = n ? n k ? 1 , k > 0 n^k = n * n^{k-1} ,k > 0?nk=n?nk?1,k>0
n k = 1 , k = 0 n^k = 1 , k = 0?nk=1,k=0

double power(int n,int k) {if (k > 0)return n * power(n, k - 1);else if (k == 0)return 1.0;//遞歸的出口k=0elsereturn 1.0 / power(n, -k); } int main() {int n = 0;int k = 0;scanf("%d%d", &n, &k);printf("%lf\n", power(n, k));return 0; }

7遞歸求斐波那契數列

遞歸和非遞歸分別實現求第n個斐波那契數

輸入輸出示例

輸入：5

輸出：5

解題思路

1 1 2 3 5 8 13 21 34 55 89 . . . 1\quad 1\quad 2\quad 3\quad 5\quad 8\quad 13\quad 21\quad 34\quad 55\quad 89\quad ...?1123581321345589...

代碼邏輯

遞歸：

F i b ( n ) = F i b ( n ? 1 ) + F i b ( n ? 2 ) , n > 2 Fib(n) = Fib(n-1) + Fib(n-2) , n>2?Fib(n)=Fib(n?1)+Fib(n?2),n>2
F i b ( 1 ) = F i b ( 2 ) = 1 Fib(1) = Fib(2) = 1?Fib(1)=Fib(2)=1

非遞歸：

上一次的b換成這一次的a

上一次的c換成這一次的b

如此循環，就可以從前往后一個一個求。

int Fib(int n) {if (n > 2)return Fib(n - 1) + Fib(n - 2);elsereturn 1; }

但是這個方法效率是非常低的，當數字特別大時，層層拆分下來，時間效率是?O ( 2 n ) O(2^n)?O(2n)。

根據公式可知，第三個斐波那契數可由前兩個得到，我們利用這個規律

int Fib(int n) {if (n <= 2)return 1;int a = 1;int b = 1;int c = 1;//n=3時不用運算while (n >= 3)//從頭開始移動n-2次，n=3時不用{c = a + b;a = b;//b賦值給ab = c;//c賦值給b n--;}return c; }int main() {int n = 0;scanf("%d", &n);printf("%d",Fib(n));return 0; }

經典問題

漢諾塔問題

漢諾塔，小時候游戲機上經常看別人玩的，自己玩到三四局就玩不下去了的那款游戲。當然如果你覺得非常簡單，小時候能玩的行云流水，那你有本事到我面前說，禮貌謝謝（狗頭保命）。

游戲規則

有三根柱子，分別為A、B、C ，A柱上從上到下依次排列著由小到大的圓盤，我們需要把圓盤從A柱按照同樣的擺放順序放到C柱上，期間我們可以借助B柱。

• 每次只能挪動一個且是最上面的圓盤
• 按照從上到下依次是由小到大的順序擺放。

解題思路

假設由N個盤子，只需要考慮第?N N?N個盤子和其上?N ? 1 N-1?N?1個盤子的整體。顯然思路就是，第?N N?N個是要放在?C C?C柱上的，

首先將?N ? 1 N-1?N?1個整體是先放在?B B?B柱上；

其次將第?N N?N個放在?C C?C柱上；

最后將?N ? 1 N-1?N?1個整體放到?C C?C柱上。

即：第?N N?N個?A → B A\rightarrow B?A→B，?N ? 1 N-1?N?1個整體?A → B → C A\rightarrow B\rightarrow C?A→B→C?。然后再考慮?N ? 1 N-1?N?1個中把第?N ? 1 N-1?N?1個當作最后一個，其上?N ? 2 N-2?N?2個當作整體，到最后只剩一個直接放到?C C?C柱上。這便是遞歸的整體思路。

void move(int n, int x, int z) {printf("%d盤：%c->%c\n", n, x, z); } void hannoi(int n, char x, char y, char z) {if (n == 1)move(n, x, z);else{hannoi(n - 1, x, z, y);move(n, x, z);hannoi(n - 1, y, x, z);} } int main() {int input = 0;do {printf("輸入盤數開始測試（0. 退出測試）\n");scanf("%d", &input);switch (input){case 0:break;default:hannoi(input, 'A', 'B', 'C');break;}} while (input);return 0; }

青蛙跳臺階

游戲規則

??初階版本

? 青蛙一次可以跳一級臺階，也可以跳兩級臺階。求該青蛙跳n級臺階共有多少種跳法？

??進階版本

? 青蛙一次可以跳一級臺階，也可以跳兩級臺階，……，也可以跳n級臺階，求該青蛙跳上n級臺階的跳法種數。

解題思路

我們反向思考，當青蛙跳到最高階?N N?N階時，他是怎么跳到第?N N?N階的呢？

有兩種情況，

• 從第?N ? 1 N-1?N?1階，跳到第?N N?N階，最后一次跳一階。
• 從第?N ? 2 N-2?N?2階，跳到第?N N?N階，最后一次跳兩階。

圖中用灰框框出的部分，是最后一次跳一階的，其余的是最后一次跳兩階的。

很顯然，除了這兩種情況，別無他法。所以計算青蛙

跳到?N N?N階的方法數?= =?=?跳?N ? 1 N-1?N?1階的方法數?+ +?+?跳?N ? 2 N-2?N?2?階的方法數。

同樣，圖中用灰框框出的部分，也代表的是跳?N ? 1 N-1?N?1階的方法數，其余的是跳?N ? 2 N-2?N?2?階的方法數。

這其實就是斐波那契數列。

int fib(int n) {if (n > 1)return fib(n - 1) + fib(n - 2);elsereturn 1; }

?

總結

以上是生活随笔為你收集整理的函数的参数、返回、调用、递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。