遞歸和迭代的差異

簡單對比一下遞歸和迭代的差異，針對全排列問題，一個用遞歸實現(xiàn)，一個用迭代（深度優(yōu)先，廣度優(yōu)先）的方式分別實現(xiàn)，均在相同計算機環(huán)境下比較。

題目：力扣-46.全排列
給定一個不含重復(fù)數(shù)字的數(shù)組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。
示例 1：
輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
輸入：nums = [0,1]
輸出：[[0,1],[1,0]]

實驗：

依次測試[1],[1,2],[1,2,3],…,[1,…,10]算例，記錄兩個方法所用時間，結(jié)果如圖所示。算法運行時間限制60s，超過即停止。

結(jié)論： 迭代（深度優(yōu)先）和遞歸差不多，與預(yù)期相符；迭代（廣度優(yōu)先）速度差很多，代碼實現(xiàn)是一方面，廣度優(yōu)先循環(huán)次數(shù)遠(yuǎn)遠(yuǎn)多余前面兩者。總體而言：

• 遞歸現(xiàn)實最為簡潔，沒有無效搜索，缺點是難以debug，問題復(fù)雜以后需要一定經(jīng)驗；
• 迭代（深度優(yōu)先）教易理解和調(diào)試，推薦；
• 迭代（廣度優(yōu)先）慎用！！！

實驗代碼：

from time import time
import matplotlib.pyplot as plt
from tqdm import trange

def recursion(nums):
    '遞歸'
    res = []
    def backtrack(nums, tmp):
        if not nums:
            res.append(tmp)
            return 
        for i in range(len(nums)):
            backtrack(nums[:i] + nums[i+1:], tmp + [nums[i]])
    backtrack(nums, [])
    return res

def iteration_dfs(nums):
    '迭代循環(huán) —— 深度優(yōu)先'
    res = []
    Queue = [[i] for i in nums]
    while Queue:
        q = Queue.pop(-1)
        if len(q) == len(nums):
            res.append(q)
            continue
        for i in nums:
            if i not in q:
                q_ = q[:]
                q_.append(i)
                if q_ not in Queue:
                    Queue.append(q_)
    return res
            
def iteration_bfs(nums):
    '迭代循環(huán) —— 廣度優(yōu)先'
    res = []
    Queue = [[i] for i in nums]
    while Queue:
        q = Queue.pop(0)
        if len(q) == len(nums):
            res.append(q)
            continue
        for i in nums:
            if i not in q:
                q_ = q[:]
                q_.append(i)
                if q_ not in Queue:
                    Queue.append(q_)
    return res

x = list(range(1,11))
y1 = []
y2 = []      
for i in trange(1,11):
    input = list(range(i))
    s1 = time()
    res1 = recursion(input)
    s1time = time()-s1
    y1.append(s1time) 
    s2 = time()
    res2 = iteration_dfs(input)
    s2time = time()-s2
    y2.append(s2time)   
    s3 = time()
    res3 = iteration_bfs(input)
    s3time = time()-s3
    y3.append(s3time)   

plt.plot(x,y1,color='b',label='recursion')
plt.plot(x,y2,color='g',label='iteration_dfs')
plt.plot(x,y3,color='r',label='iteration_bfs')
plt.legend()
plt.xlabel('問題規(guī)模')
plt.ylabel('時間(s)')
# plt.savefig('results.jpg')