我認為可以將遞歸函數(shù)分為兩種情況，一種是有返回值的，一種是沒有返回值的（僅做結(jié)束遞歸用），我分別給起了名字，有返回值的叫尋找初心，無返回值的叫開枝散葉。下面分別討論一下。

有返回值，尋找初心

大家很愛使用斐波那契數(shù)列做例子，那我也不例外，但是也有例外的地方。一般直接寫出如下代碼：

def dfs(n):
    if n == 1 or n == 2:
        return 1
    return dfs(n - 1) + dfs(n - 2)

其實這樣并不利于理解，因為這是理解這個遞歸之后的人寫出的代碼。那怎么樣寫可以理解起來簡單一些呢？先給出代碼，稍后給出解釋。

def dfs(n):
    if n == 1 or n == 2: #3 搜索尋得初心，返回
        return 1 #3 搜索尋得初心，返回
    a = dfs(n-1) #1 知道它會接著往下搜索即可
    b = dfs(n-2) #1 知道它會接著往下搜索即可
    res = a + b #2 不想遞歸，只要我知道了a+b，就是我要的結(jié)果
    return res 

我認為寫出這個代碼，應(yīng)該是這樣的思路。

• 一開始你定義好了一個函數(shù)dfs，輸入n，返回斐波那契數(shù)列的第n個數(shù)字res。
• 根據(jù)斐波那契數(shù)列的性質(zhì)你會想，要是知道第n-1和第n-2個數(shù)字就好了，可惜并不知道，但是好像可以使用剛才定義的函數(shù)表示為dfs(n-1)和dfs(n-2)。
• 這樣表示可以嗎？好像表示完了還得知道第n-3和第n-4個數(shù)字，這樣寫的話，這個函數(shù)就會一直往下找哎，還得知道第n-5和第n-6個數(shù)字。
• 如果它能一直往下找也挺好的哎，我知道數(shù)列的前幾個數(shù)，找到最后沒準兒可以哎。
• 那么需要知道數(shù)列前幾個數(shù)呢，好像知道一個不行，因為dfs(3) = dfs(2) + dfs(1)，如果只知道dfs(1)，那dfs(2)還會繼續(xù)往下找，dfs(2) = dfs(1) + dfs(0)，dfs(0)不知道，繼續(xù)往下找，接下來更沒有知道的了。那兩個可以嗎？好像可以，按剛才的思路，有兩個的話，就不用繼續(xù)往下找了。
• 那我們在函數(shù)每次往下找的時候判斷一下好了，如果是找數(shù)列第一個數(shù)和第二個數(shù)，就返回1。至此，初心找到了，這個函數(shù)，好像差不多了。你應(yīng)該是有點兒懵，但是也有點懂了的感覺。

無返回值，開枝散葉

簡單理解一下，就是利用遞歸，實現(xiàn)排列和組合。先只給出排列的例子：

# 排列 permutation
def dfs(self, result, nums, path):
    if not nums:
        result.append(path)
        return # 沒有返回值，只是為了停止遞歸
    for i in range(len(nums)):
        self.dfs(result, nums[:i] + nums[i+1:], path + [nums[i]])

nums = [1,2,3]
result = []
self.dfs(result, nums, [])
return result
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

這個其實只要關(guān)注path就可以清楚理解遞歸干的事兒。