遞回

一，什么是遞回

1.遞回的詳細定義

程式呼叫自身的編程技巧稱為遞回（ recursion），遞回做為一種演算法在程式設計語言中廣泛應用， 一個程序或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼量，遞回的能力在于用有限的陳述句來定義物件的無限集合，一般來說，遞回需要有邊界條件、遞回前進段和遞回回傳段，當邊界條件不滿足時，遞回前進；當邊界條件滿足時，遞回回傳，

2.遞回的簡單理解

所謂遞回從字面意思上就可以看出來，遞回可以拆分成傳遞和回呼兩個程序，遞回是一個不斷呼叫自身，并回傳結果的過稱，當然遞回也不可能無限制的呼叫回傳，需要條件來控制遞回，并且需要有程式實作不斷地向遞回的條件靠攏，否則就算有遞回的條件，也只是不斷地在原地踏步，這也就指出了遞回的兩個條件

3.遞回的基本思想

遞回的基本思想，是把規模較大的一個問題，分解成規模較小的多個處理方法相同的子問題去解決，而每一個子問題又可以繼續拆分成多個更小的處理方法相同的子問題，

最重要的一點就是假設所有的子問題已經解決了，現在要基于已經解決的子問題來解決當前問題；遞回就是一個逐層深入的程序，打個比方就好比，就相當于與我們編程的時候遇到一個特別難的問題，我自己不能解決，我們需要求助他人，這個難題很多人都解決不了，最后傳到了編程界最牛的人手里被解決了（這就好比遞回的限制條件，如果大牛都解決不了那不崩了），當大牛解決問題后答案被返還回我，這樣這個問題就被我解決了，這就是遞回，

4.遞回存在的兩個必要條件

• 存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，

• 每次遞回呼叫之后越來越接近這個限制條件，

二, 如何使用遞回以及使用程序中的一些問題

1.舉例練習遞回

例1 接受一個整形值（無符號），按順時針列印它的每一位，例如：輸入：1234，輸出1 2 3 4.

#include<stdio.h>

void print(int n)
{
	if (n > 9)
	{
		print(n / 10);
	}
	printf("%d\n", n % 10);
}

int main()
{
	int num = 1234;
	print(num);
	return 0;
}

代碼分析：這是一個很簡單的代碼，目的是輸入1234，輸出1 2 3 4 首先進入函式print,當n大于9時執行程式，否則執行下一句程式，當輸入1234時，進入判斷條件，在一次呼叫print函式，并將n/10,變成123，在一次進入print函式，執行判斷陳述句，變成12，再重復上述程序直到n = 1,時，再一次進入print程式時不滿足條件，執行下面條件輸出1，然后回傳上一級輸出2，依次輸出3，4，具體程序如圖所示

例2 撰寫函式不允許創建臨時變數，求字串長度，

首先，我們先用一個創建臨時變數代碼實作求字串長度的代碼，來進一步加深不用創建臨時變數求字串長度的方法

#include<stdio.h>

int mn_strlen(char* p)
{
	int count = 0;
	while (*p != '\0')
	{
		p++;//將指標后移一位
		count++;//如果不是\0就是自增1
	}
	return count;
}

int main()
{
	char arr[] = "bit";
	printf("%d\n", mn_strlen(arr));
	return 0;
}

代碼分析：改代碼模擬實作了strlen的功能，靈活的運用了指標，strlen函式的原理是：找到字串結束標志\0, 并統計\0前所有字符的個數，

下面我們來看看不用創建臨時變數，來實作求字串長度的方法，

#include<stdio.h>

int  MN_strlen(char* p)
{
    if (*p == '\0')
	{
		return 0;
	}
	else
	{
		return 1 + MN_strlen(p + 1);
	}
}

int main()
{
	char arr[] = "bit";
	printf("%d\n", MN_strlen(arr));
	return 0;
}

例3 ：求n的階乘，（不考慮溢位）

#include<stdio.h>

int Fac(int n)
{
	if (n <= 1)
	{
		return 1;
	}
	else
	{
		return n * Fac(n - 1);
	}
}

int main()
{
	int input;
	printf("請輸入一個數:\n");
	scanf("%d", &input);
	printf("%d 的階乘為 %d\n", input, Fac(input));
	return 0;
}

代碼分析: 當n小于等于1時n的階乘為1，當n大于1時n的階乘為n乘n-1的階乘，以此類推n-1的階乘等于n-1乘n-2的階乘，直到n等于1為止，回傳n等于1的階乘，從而回傳n等于二的階乘，直到回傳n等于n-1的階乘，進而求出n階乘，

例4 ：求第n個斐波那契數， （不考慮溢位）

#include<stdio.h>

int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n - 2);
	}
}

int main()
{
	int input;
	printf("請輸入一個數:\n");
	scanf("%d", &input);
	printf("第n個斐波那契數為%d\n", fib(input));
	return 0;
}

在運算例3，例4時可能會發生一些問題

• 當我們運行fib這個函式時，如果我們想要求第50個或者更大的數時我們會發現，我們通常會需要更長的時間，
• 當我們運行Fac這個函式時，如果我們想要求1000的階乘或者更大的數時我們會發現程式崩潰了

為什么呢？

我們發現fib在執行程序中有很多計算步驟都是重復的，下面我們將代碼修改一下：

int count = 0;
int fib(int n)
{
	if (n == 3)
	{
		count++;
	}
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n - 2);
	}
}

最后我們可看以看到輸出的count是一個很大的數，這說明了這種演算法在計算上有很多重復，這也是遞回演算法的缺點，遞回演算法的優點在于代碼簡潔，易于理解，但缺點在于時間和空間消耗較大，并且有可能發生堆疊溢位現象，遞回中又有很多計算都是重復的，遞回的本質時把一個問題分解成兩個或多個小 問題，多個小問題存在重疊的部分，即存在重復計算，正如上面斐波那契數列的遞回實作，

在除錯fib函式的時候，如果你的引數比較大，那就會報錯：stack overflow (堆疊溢位)這樣的資訊，系統分配給堆疊的空間是有限的，如果出現死了死回圈或者死遞回，這樣有可能導致一直開辟空間，最終導致堆疊空間耗盡的情況，這種現象我們成為堆疊溢位，

那么如何解決這種問題呢？

三, 如何解決堆疊溢位問題，并對程式進行優化，

有以下兩種方法：
第一種就是：

1. 將遞回改為尾遞回的形式：

那么什么是尾遞回呢，以下內容是對尾遞回的書面解釋：如果一個函式中所有遞回形式的呼叫都出現在函式的末尾，我們稱這個遞回函式是尾遞回的，當遞回呼叫是整個函式體中最后執行的陳述句且它的回傳值不屬于運算式的一部分時，這個遞回呼叫就是尾遞回，尾遞回函式的特點是在回歸程序中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼，下面我們通過一幅圖片來解釋一下什么時尾遞回，

當編譯器測到一個函式呼叫是尾遞回的時候，它就覆寫當前的活動記錄而不是在堆疊中去創建一個新的，編譯器可以做到這點，因為遞回呼叫是當前活躍期內最后一條待執行的陳述句，于是當這個呼叫回傳時堆疊幀中并沒有其他事情可做，因此也就沒有保存堆疊幀的必要了，通過覆寫當前的堆疊幀而不是在其之上重新添加一個，這樣所使用的堆疊空間就大大縮減了，這使得實際的運行效率會變得更高，實際上尾遞回并沒有像普通遞回那樣每次都會在堆疊上開辟新的空間，而是選則去覆寫之前的空間，這樣下來最終相當于尾遞回最后只開辟了一次堆疊空間，只回傳了一次，這樣大大減少了堆疊空間的開辟，提高了空間的利用率，也減少了時間的浪費，

下面我們用尾遞回來重新改寫一下n的階乘，

#include<stdio.h>

int fab(int n, int a)//每次呼叫函式時都將a初始化為1
{
	if (n < 0)
	{
		return 0;
	}
	if (n == 0)
	{
		return 1;
	}
	if (n == 1)
	{
		return a;//呼叫尾遞回最后將a的值回傳
	}
	if (n > 1)
	{
		return fab(n - 1, n * a);//開始呼叫遞回直到n=1為止
	}
}

int main()
{
	int input;
	printf("請輸入一個數: >\n");
	scanf("%d", &input);
	int ret = fab(input, 1);
	printf("%d\n", ret);
	return 0;
}

這樣通過圖片和實體，理解起來應該會很容易

第二種就是：

2. 將遞回改為非遞回的形式：

將遞回改為非遞回的形式：又細分為下面兩種方法， 而這里只總結第一種方法，
1.迭代的演算法：所謂迭代簡單的理解理解就是重復的反饋活動，就是重復執行同一演算法，并將上一次運算的結果，作為下一次運算的初始值，直到回圈滿足條件，停止并回傳相應的值，

迭代相比較遞回具有的優點是，代碼運行效率高，時間和空間上沒有多余的開銷，相比較于遞回的不足之處在于代碼沒有遞回簡潔，通俗易懂，

下面我們用迭代來寫一下n的階乘和第n個斐波拉契數，

//迭代法求n的階乘
int fac(int n)
{
	int i = 0;
	int ret = 1;
	for (i = 1; i <=  n; i++)
	{
		ret *= i;
	}
	return ret;
}

int main()
{
	int input;
	printf("請輸入一個數:\n");
	scanf("%d", &input);
	printf("%d 的階乘為 %d\n", input, fac(input));
	return 0;
}

//迭代法求第n個斐波那契數
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 input;
	printf("請輸入一個數:\n");
	scanf("%d", &input);
	printf("第n個斐波那契數為%d\n", fib(input));
	return 0;
}

使用這種方法可以很好的解決遞回的一些缺點，并且很好的解決了堆疊溢位的問題，

2.借助堆疊模擬遞回的執行程序，這種方法就不具體介紹了，因為我還沒有學資料結構，自己的理解也并不是很好，后期學了資料結構，就在寫一篇關于這種方法的博客吧，

四, 那么遞回和迭代我們應該如何選擇呢

1.許多問題是以遞回的形式解決的，這是因為他比非遞回的形式更為清晰，

2.但是這些問題的迭代形式實作往往比遞回實作效率更高，雖然代碼可讀性稍微差一些，

3.當一個問題相當復雜，難以用迭代實作時，此時遞回實作的簡潔性便可以彌補它所帶來的運行時的開銷，

五，函式遞回的幾個經典題目

• 漢諾塔問題
• 青蛙跳臺階問題