To iterate is human, to recurse, divine.
人理解迭代，神理解遞歸。

人的思維，一般是迭代(iteration)。比如人都是先學習加減法，再學習乘除法，最后學習微積分。數(shù)學歸納法其實就是一種迭代，從一個簡單的起點，推廣到一般情況。

遞歸(recursion)，則是一種反人類的逆向思維。作為一個程序員，每次使用遞歸時，代碼總是簡潔到讓自己心虛，因為這種思維邏輯甚至是反常識的。

什么是遞歸

遞歸，在數(shù)學與計算機科學中，是指在函數(shù)的定義中使用函數(shù)自身的方法。也就是說，遞歸算法是一種直接或者間接調用自身函數(shù)或者方法的算法。

通俗來說，遞歸算法的實質是把問題分解成規(guī)?？s小的同類問題的子問題，然后遞歸調用方法來表示問題的解。

遞歸的基本原理

第一：每一級的函數(shù)調用都有自己的變量。

第二：每一次函數(shù)調用都會有一次返回。

第三：遞歸函數(shù)中，位于遞歸調用前的語句和各級被調用函數(shù)具有相同的執(zhí)行順序。

第四：遞歸函數(shù)中，位于遞歸調用后的語句的執(zhí)行順序和各個被調用函數(shù)的順序相反。

第五：雖然每一級遞歸都有自己的變量，但是函數(shù)代碼并不會得到復制。

第一要素：明確你這個函數(shù)想要干什么。先不管函數(shù)里面的代碼什么，而是要先明白，你這個函數(shù)的功能是什么，要完成什么樣的一件事。

第二要素：尋找遞歸結束條件。我們需要找出當參數(shù)為啥時，遞歸結束，之后直接把結果返回，請注意，這個時候我們必須能根據(jù)這個參數(shù)的值，能夠直接知道函數(shù)的結果是什么。

第三要素：找出函數(shù)的等價關系式。我們要不斷縮小參數(shù)的范圍，縮小之后，我們可以通過一些輔助的變量或者操作，使原函數(shù)的結果不變。

具體地說，如果遞歸函數(shù)調用自己，則被調用的函數(shù)也將調用自己，這將無限循環(huán)下去，除非代碼中包含終止調用鏈的內容。通常的方法將遞歸調用放在if語句中。

遞歸的強大之處在于它允許用戶用有限的語句描述無限的對象。因此，在計算機科學中，遞歸可以被用來描述無限步的運算，盡管描述運算的程序是有限的。這一點是循環(huán)不太容易做到的。

編寫正確的遞歸算法，一定要有 ”歸“ 的步驟，也就是說遞歸算法，在分解問題到不能再分解的步驟時，要讓遞歸有退出的條件，否則就會陷入死循環(huán)，最終導致內存不足引發(fā)棧溢出異常。