遞迴—看這篇就夠了
層遞式是什麼意思
遞迴——看這篇就夠了
引子
我懷著無比激動的心情寫下這篇文章，因為我它介紹是一種無比優雅的問題解決方案——
遞迴
相信很多同學在學習遞迴的時候都會有這樣一個疑惑，這個東西究竟是如何自己呼叫自己的，大佬寫幾行程式碼就實現了複雜的功能。今天我們就來好好討論這個優雅的遞迴。
一、定義
在數學與計算機科學中，遞迴（Recursion）是指在函式的定義中使用函式自身的方法。實際上，遞迴，顧名思義，其包含了兩個意思：遞 和 歸，這正是遞迴思想的精華所在。
用人話來說就是函式呼叫自己。
二、遞迴的三大要素
明確這個函式作用
先不管程式碼，我們首先要明白的是我們要這個函式幹什麼。 例如我定義一個函式
void
f
（
int
i
）{
//計算階乘
}
這個函式就是計算n的階乘。好啦，現在我們已經明白了這個函式的作用，我們來看看第二要素吧。
找到終止條件
我們需要給函式一個終止條件，總不能讓函式一直在呼叫自己，在函式‘遞’的這個過程結束後，拿著結果進行‘歸’的過程。
void
f
（
int
i
）{
if
（
i
==
1
）{
return
1
；
}
}
由上面的栗子我們可以直接看出當i=1時候，函式的返回值相信大家非常清楚。那我們現在來看看第三要素吧，
提取重複的邏輯
不斷的縮小範圍，我們可以使用一些變數或操作使原函式結果不變。
好啦，現在重要到第三步了，當然這一步也是有一丟丟難的，找不清等價關係式沒關係，因為你不是天才，你需要多接觸幾道題，我在後面也會增加10道遞迴演算法題的。話不多說我們看程式碼。
void
f
（
int
i
）{
if
（
i
==
1
）
//遞迴結束的條件
return
1
；
//函式的等價操作
return
f
（
i
-
1
）
*
i
；
}
f（i-1）就是函式的等價式，我們透過不斷縮小i的值，這樣範圍就變小了。為了不改變原函式的結果，我們還需要進行*i。
三、遞迴執行
看到這裡，我相信大家對於遞迴的定義和遞迴的要素都已經很清楚，那麼，我們接下來我們就來談談遞迴的執行吧。
遞迴程式的執行過程可以分為兩個階段
遞推階段
遞迴每一次都是基於上一次進行下一次的執行。
回溯階段
當遇到終止條件，則從最後往回一級一級的把值返回來。
我們還是以求i的階乘為例子吧。
void
func
（
int
i
）{
if
（
i
==
1
）
//遞迴結束條件
return
1
；
return
f
（
i
-
1
）
*
i
；
//關係等價式
}
透過畫圖我們可以清楚的看到遞迴的執行過程
透過看圖我們不難發現
func()函式
一直在呼叫自己，當i=1時，遞推結束，函式開始一層一層回溯。所以在使用遞迴來解決問題時候我們一定要注意遞迴結束的條件，如果沒有結束條件的話，無限遞迴會造成的堆疊溢位的。
四、經典遞迴問題實戰
（1）斐波拉契數列
斐波納契數列，又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、……
這裡我們使用兩種方法來解決這個問題，透過這兩種方式，我想大家能夠感受到遞迴的妙處。
非遞迴實現方法
//非遞迴實現
int
func
（
int
n
）{
if
（
n
==
1
||
n
==
2
）{
return
1
；
}
int
result
=
-
1
；
int
first
=
1
；
int
second
=
1
；
for
（
int
i
=
3
；
i
<=
n
；
i
++
）
{
// 迴圈
result
=
first
+
second
；
first
=
second
；
second
=
result
；
}
return
result
；
}
遞迴實現
int
func
（
int
n
）{
if
（
n
==
1
||
n
==
2
）{
//遞迴出口
return
1
；
}
return
func
（
n
-
1
）
+
func
（
n
-
2
）；
}
我們不難發現使用使用遞迴的程式碼比非遞迴的程式碼要簡潔的多，同時也能看出遞迴的程式碼我們透過迴圈也能完成。現在引出了我們的下一個問題。
遞迴和迴圈我們應該怎麼選擇？
在我看來，遞迴和迴圈解決問題都是一樣的，遞迴能使解決方案更加清晰，但是遞迴在效能上沒有優勢。實際上，在開發中，有些情況使用迴圈比遞迴顯得更好。如果使用迴圈，程式的效能將會更好；但是使用遞迴，程式將會更加容易理解。如何選擇看什麼對你更加
重要
。
好啦！今天的文章就到這裡啦，這篇文章上個禮拜就開始寫了，奈何最近考試太多了。好在，複習了一個禮拜，感覺自己答的還是可以的。看來考前突擊很重要的（敲重點）。今天難得有空，終於把文章寫完了。如有錯誤歡迎大家指出。如果本篇文章對你有收穫，那麼就點個
再看
再走吧。微信搜Arenly我們一起進步吧。
★ 作者 ：Arleny
CSDN ： Keiy_
”
喜歡就點個關注吧，我們下期再見。
