再帰を走らせた時の道筋

再帰を走らせた時の道筋が知りたくなったため、考察してみました。
具体的には、以下のPythonコードで表される再帰を考えます。

# -*- coding: utf-8 -*-
def recShow(n):
    if n == 5:
        return
    else:
        recShow(n + 1)
        recShow(n + 1)

recShow(1)

これが、どのような道筋をたどるのかを知りたかったため、
試行錯誤し、以下のようにしてみました。

# -*- coding: utf-8 -*-
def recShow(n, lst):
    if n == 5:
        lst.append("ret")
        return
    else:
        newlst = lst[:]
        newlst.append("a%d"%n)
        recShow(n + 1, newlst)
        newlst.append("b%d"%n)
        recShow(n + 1, newlst)
        print newlst
        
print ""
lst = []
recShow(1, lst)

出力は以下のようになります。

['a1', 'a2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'a3', 'b3']
['a1', 'a2', 'b2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'b2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'b2', 'a3', 'b3']
['a1', 'a2', 'b2']
['a1', 'b1', 'a2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'a3', 'b3']
['a1', 'b1', 'a2', 'b2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'b2', 'a3', 'b3']
['a1', 'b1', 'a2', 'b2']
['a1', 'b1']