3.6　遞歸函數

在編程語言中，如果函數直接或間接調用函數自身，則該函數被稱為遞歸（Recursion）函數。遞歸作為一種算法在編程語言中被廣泛應用。有些現實問題不借助遞歸的話，求解過程會非常復雜。

3.6.1　使用遞歸函數求解斐波那契數列

遞歸往往只需少量的代碼就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有退出條件，否則會進入無限循環而無法退出。

舉一個數學中的例子，斐波那契數列是：1，1，2，3，5，8，13，21，34，55，89，144……以此類推，我們會發現在這個數列中，后一個數等于前面兩個數之和（1=1+0，2=1+1，3=1+2……）。這個數列的規律在自然界中也很有代表性，如兔子自然繁殖數量的規律。

如果想求解斐波那契數列，那么最直接的方式是借助遞歸函數來求解。首先分析數列的遞歸表達式：

此函數解析式是一個分段函數，其中第二段是一個遞歸函數，需要函數調用自身。下面是遞歸函數求解斐波那契數的示例程序3-8。

示例程序3-8　遞歸函數實現斐波那契數列：chapter03\code08\func.go

在示例程序3-8中，第04行定義了一個名為fib的函數，接收一個int64類型的變量，同時返回一個int64類型的值。第05～07行用到了邏輯控制中的if條件判斷，其中if n <=1是遞歸的退出條件。第08行是體現遞歸的地方，fib函數調用自身。

一般來說，在編程語言中，函數調用是通過棧（Stack）這種數據結構來實現的：每當進入一個函數調用，棧就會加一層棧幀；每當函數調用結束后返回，棧就會減一層棧幀。由于棧的大小是有限的，因此如果遞歸調用的次數過多，就可能會導致棧內存溢出的情況。另外，由于遞歸中間的臨時運算結果并沒有暫存，因此計算速度也比較慢。

遞歸函數雖然可以簡化程序，讓程序代碼更加具有可讀性，但是如果遞歸的調用層次過多，那么執行效率會非常低，也非常耗時，例如用遞歸計算fib(50)會非常耗時。此時需要用其他的非遞歸方式來實現，以提高效率。

3.6.2　使用循環代替遞歸的方法

遞歸函數也可以利用非遞歸的方法來實現。下面給出計算斐波那契數列的非遞歸改進版本，以提高計算速度，如示例程序3-9所示。

示例程序3-9　用非遞歸函數來實現斐波那契數列：chapter03\code08\func2.go

在示例程序3-9中，實際上是用循環的方式來替換遞歸的方式，由于中間的值都暫存在臨時變量中，因此這種方式的計算效率與遞歸方式的計算效率要高不少。