思考過程3

長さ n の文字列を食わせて長さ n+1 の文字列のリストを得る関数はできた。

def f(s):
    return map(lambda i: s[:i] + str(len(s) + 1) + s[i:], range(0, len(s) + 1))

例えば、"123456" を食わせると

f('123456')
['7123456', '1723456', '1273456', '1237456', '1234756', '1234576', '1234567']

という出力結果が得られる。
が、根本的な部分が解決できていない。リストを渡したらリストが返ってくるような関数にしないと、再帰処理が面倒になるのね。そこさえクリアすれば、ゴールは近い。