頭文件
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
函數遞歸什麼是遞歸？
先看看 XX 百科的定義：
程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸作為一種算法在程序設計語言中廣泛應用。一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重複計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
這種定義看完是不是一臉懵逼？
不舉例子一定不知道他在說什麼，這種定義有還不如沒有，直接上例題說不定還能讓人更好理解
那麼，遞歸到底是什麼？
我們換個詞，遞歸換成回歸，或者遞迴
設想一個場景：n 個人排成了一條隊，第 1 個人在隊尾，第 n 個人在隊首
現在第 1 個人想知道第 n 個人名字，怎麼辦？
第 1 個人讓前面的人幫忙傳話，一人接一人的傳
內容是 「我想知道你的名字」，傳到第 n 個人耳朵裡
第 n 個人在一張紙條上寫上自己的名字，一人接一人的遞迴來
遞迴到第 1 個人手裡，於是第 1 個人知道了第 n 個人的名字
這就是遞歸
根據涉及有限步數的規則或公式，通過對一個或多個前面的元素進行運算來確定一系列元素（例如數字或函數）
遞歸的主要思考方式在於：把大事化小
把大事（自己跑隊首去要人名字）化小（叫人傳話遞迴來）
遞歸的兩個必要條件：
存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續舉慄說明：
最簡單的遞歸
int main()
{
main();
return 0;
}很容易就看出，這是一個無限遞歸
會產生 Stack overflow 的錯誤
Stack overflow，就是常說的棧溢出
內存的劃分如下表所示：
名稱作用棧區（stack）存放局部變量、函數形參堆區（heap）存放動態開闢的內存（malloc，calloc）靜態區存放全局變量（static修飾的變量）常量區存放常量代碼區存放只讀代碼調用一次 main 函數，就會向棧區申請一塊空間，main 函數中又再調用 main 函數，無限遞歸後，棧區空間耗盡，於是棧溢出
有一個網站叫 stackoverflow.com，這是程式設計師的知乎
練習練習 1接收一個整型值（無符號），按照順序列印它的每一位
例如輸入 1234 ,輸出 1 2 3 4
void print(int n)
{
if (n > 9)//能停下來的條件
{
print(n / 10);//可以滿足那個條件
}
printf("%d ", n % 10);
}
int main()
{
unsigned int num = 0;
scanf("%d", &num);//1234
//遞歸
print(num);
return 0;
}遞歸思想：
print(1234)
print(123) 4
print(12) 3 4
print(1) 2 3 4
練習 2編寫函數不允許創建臨時變量，求字符串長度
int my_strlen(char* str)
{
//計算字符串（bit - b i t \0）的長度
//str 存的是 arr 第一個元素的地址
//判斷 *str的值，不為 \0，就 str++
//往右邊挪一個長度往第二個元素找
int count = 0;
while (*str != '\0')
{
count++;
str++;
}
return count;
}上面代碼用到了臨時變量 count，但規定了不能創建臨時變量
遞歸的函數，仍然用遞歸的方法解決問題
遞歸思想：
my_strlen("bit")
1+my_strlen("it")
1+1+my_strlen("t")
1+1+1+my_strlen("")
1+1+1+0
= 3重新寫代碼：
int my_strlen(char* str)
{
if (*str != '\0')
return 1+ my_strlen(str+1);
else
return 0;
}
int main()
{
char arr[] = "bit";
//int len = strlen(arr);
//printf("%d\n", len);
//模擬實現一個 strlen 函數
int len = my_strlen(&arr);
printf("len = %d\n", len);
return 0;
}
練習 3求 n 的階乘（不考慮溢出）
int factorial(int n)
{
if (n <= 1)
return 1;
else
return n * factorial(n - 1);
}
int main()
{
int n = 0;
int ret = 0;
printf("請輸入一個數:>");
scanf("%d", &n);
ret = factorial(n);
printf("%d 階乘是 %d\n", n, ret);
return 0;
}
練習 4遞歸與迭代
求第 n 個斐波那契數（不考慮溢出）
1，1，2，3，5，8，13，21，34，55，...
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
//這樣寫效率非常低，試試 n = 50，看看要花多長時間算出來
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
//TDD - 測試驅動開發
ret = Fib(n);
printf("ret = %d\n", ret);
return 0;
}可以加一點代碼
if (n == 3)
{
count++;
}
printf("%d\n", count);查看求第 40 個斐波那契數的時候，第 3 個斐波那契數被重複計算了多少次
答案是 39088169 次
重複計算量非常大，在這裡，遞歸不是一個好辦法
重新寫代碼：
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
ret = Fib(n);
printf("ret = %d\n", ret);
return 0;
}這樣運算速度就快多了，循環迭代更適合求斐波那契數
總結許多問題是以遞歸的形式進行解釋的，這只是因為它比非遞歸的形式更為清晰但是這些問題的迭代實現往往比遞歸實現效率更高，雖然代碼的可讀性稍微差些當一個問題相當複雜，難以用迭代實現時，此時遞歸實現的簡潔性便可以補償它所帶來的運行時的開銷遞歸就算寫正確了，也不代表就不會出問題
void test(int n)
{
if (n < 10000)
{
test(n + 1);
}
}
int main()
{
test(1);
return 0;
}這個代碼就會棧溢出
提升函數遞歸的經典題目
漢諾塔漢諾塔問題是一個經典的問題。漢諾塔（Hanoi Tower），又稱河內塔，源於印度一個古老傳說。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，任何時候，在小圓盤上都不能放大圓盤，且在三根柱子之間一次只能移動一個圓盤。問應該如何操作？
遞歸思想：
假如只有 1 個盤子，直接從從塔 a 移動到塔 c
n 個盤子，從上到下為 1 到 n，從塔 a 移動到塔 c，以塔 b 中轉
不管中間過程如何，第 n 個盤子（最大那個），一定得想辦法先移到塔 c
既然第 n 個盤子移到塔 c，剩下的 n-1 個盤子不可能仍在塔 a，它們一定移到了塔 b
這樣，我們第一步要做的就是：
把第 n 個盤子移到塔 c，剩下的 n-1 個盤子移到塔 b
不管中間過程如何，這個邏輯是絕對正確的
下一步就變成了：
n-1 個盤子，從上到下為 1 到 n-1，從塔 b 移動到塔 c，以塔 a 中轉
重複以上過程，遞歸就出來了
偽代碼：
func:
if n!=0 then ;預定值
func(n-1, a, c, b) ;將n-1個盤子由a移動到b，以c為輔助柱子（注意參數順序）
move a[n] to c ;將a上的最後一個盤子移動到c
func(n-1, b, a, c) ;將n-1個盤子由b移動到c，以a為輔助柱子
endif ;完成代碼實現：
void hanoi(int n,char a,char b,char c)
{
if (n == 1)
{
printf("從塔%c 移到到塔%c\n", a, c);
}
else
{
hanoi(n - 1, a, c, b);//n-1個盤子，從塔a移動到塔b，以塔c中轉
printf("從塔%c 移到到塔%c\n", a, c);//將塔a的盤子移動到塔c
hanoi(n - 1, b, a, c);//n-1個盤子，從塔b移動到塔c，以塔a中轉
}
}
int main()
{
int n = 0;
printf("請輸入要從塔 a 轉移到塔 c 的盤子個數:>");
scanf("%d", &n);
hanoi(n, 'a', 'b', 'c');
return 0;
}