はじめに
再帰プログラムを書いているうちに混乱したので、再帰の仕組み（ツリーとpythonでの実現方法の関係）を調べました。ツリー自体は、いまでもOSのディレクトリとかとにかくよく見ます。再帰は想像ですが先生とかが好きで宿題とかにだされる？とりあえずざっと眺めた限り書いている人がいなさそうだったので公開します。（いるという突っ込みはなしで）
再帰関数の構造と概念図
以下は、拙作「スケルトンパズル解いてみました」 のsolve関数だけを抜き出したものです。
リストのワードが１１個、ワードを入れる連続マスが１１個の例題なので、場合の通りは、 最大$11^{11}$ ですがpossible関数を作成して、いろいろ制約条件を付け、再帰処理すれば大幅に場合の数が減ります。
階層(レベル)0のルートから始まり、レベル1～12のノードを如何に探索するかという問題です。（1992年発行の「アルゴリズムとデータ構造」では節点と書いてました。時代を感じる）ノードは、ある状態（ステート）【連続マス, ワード】を表す。たとえば、【連続マス: (1)(2,3,4), ワード: "面子"】の組み合わせのステートを表す。（たぶん、下図の緑の１丸）レベルと連続マスは同じになる。
基本的な移動は、以下の通りです。
- 下方向への遷移（レベルn+=1） -> solve関数の呼び出し
- 横方向への遷移 -> for word in Words: リスト中のワードをすべてトライ
- 上方向への遷移（レベルn-=1） -> return False
- 最深部レベル１２まで到達すると一気にreturn Trueで終了
global Renban
Renban = 0
def solve(renMasul, n):
global Renban
print(f"先頭 n:{n}")
#最深部の判定
if n >= len(renMasul):
print(f"n:{n}, 最深部")
return True
#リストからワードを順番に試す
for word in Words:
Renban += 1
print(f"連番:{Renban}, n:{n}, word:{word}")
#可能だったら次のレベルに進む
if possible(renMasul, n, word):
renMasul[n].ahead(word)
if solve(renMasul, n + 1):
return True
renMasul[n].back()
return False
概念図に書き表すと以下の通りです。なんか横にぬるぬると動くんですね
注意、return Trueはfor文の途中でも上移動するのですがうまく書けてません。あしからず
検証
強引にglobal Renbanを追加して、出力してみました。
誰かの役に立てば幸いです。
先頭 n:0
連番:1, n:0, word:都会
連番:2, n:0, word:面子
連番:3, n:0, word:風聞
連番:4, n:0, word:一風
連番:5, n:0, word:子供会
連番:6, n:0, word:都市名
連番:7, n:0, word:名調子
連番:8, n:0, word:真砂地
連番:9, n:0, word:女子大生
先頭 n:1
連番:10, n:1, word:都会
連番:11, n:1, word:面子
連番:12, n:1, word:風聞
連番:13, n:1, word:一風
連番:14, n:1, word:子供会
先頭 n:2
連番:15, n:2, word:都会
連番:16, n:2, word:面子
連番:17, n:2, word:風聞
連番:18, n:2, word:一風
連番:19, n:2, word:子供会
連番:20, n:2, word:都市名
連番:21, n:2, word:名調子
連番:22, n:2, word:真砂地
連番:23, n:2, word:女子大生
連番:24, n:2, word:地方新聞
連番:25, n:2, word:生真面目
連番:26, n:2, word:面目一新
連番:27, n:1, word:都市名
先頭 n:2
連番:28, n:2, word:都会
連番:29, n:2, word:面子
連番:30, n:2, word:風聞
連番:31, n:2, word:一風
連番:32, n:2, word:子供会
先頭 n:3
連番:33, n:3, word:都会
先頭 n:4
連番:34, n:4, word:都会
連番:35, n:4, word:面子
連番:36, n:4, word:風聞
連番:37, n:4, word:一風
連番:38, n:4, word:子供会
連番:39, n:4, word:都市名
連番:40, n:4, word:名調子
先頭 n:5
連番:41, n:5, word:都会
連番:42, n:5, word:面子
先頭 n:6
連番:43, n:6, word:都会
連番:44, n:6, word:面子
連番:45, n:6, word:風聞
連番:46, n:6, word:一風
連番:47, n:6, word:子供会
連番:48, n:6, word:都市名
連番:49, n:6, word:名調子
連番:50, n:6, word:真砂地
連番:51, n:6, word:女子大生
連番:52, n:6, word:地方新聞
連番:53, n:6, word:生真面目
先頭 n:7
連番:54, n:7, word:都会
連番:55, n:7, word:面子
連番:56, n:7, word:風聞
連番:57, n:7, word:一風
連番:58, n:7, word:子供会
連番:59, n:7, word:都市名
連番:60, n:7, word:名調子
連番:61, n:7, word:真砂地
先頭 n:8
連番:62, n:8, word:都会
連番:63, n:8, word:面子
連番:64, n:8, word:風聞
連番:65, n:8, word:一風
連番:66, n:8, word:子供会
連番:67, n:8, word:都市名
連番:68, n:8, word:名調子
連番:69, n:8, word:真砂地
連番:70, n:8, word:女子大生
連番:71, n:8, word:地方新聞
連番:72, n:8, word:生真面目
連番:73, n:8, word:面目一新
先頭 n:9
連番:74, n:9, word:都会
連番:75, n:9, word:面子
連番:76, n:9, word:風聞
連番:77, n:9, word:一風
連番:78, n:9, word:子供会
連番:79, n:9, word:都市名
連番:80, n:9, word:名調子
連番:81, n:9, word:真砂地
連番:82, n:9, word:女子大生
連番:83, n:9, word:地方新聞
先頭 n:10
連番:84, n:10, word:都会
連番:85, n:10, word:面子
連番:86, n:10, word:風聞
連番:87, n:10, word:一風
先頭 n:11
連番:88, n:11, word:都会
連番:89, n:11, word:面子
連番:90, n:11, word:風聞
先頭 n:12
n:12, 最深部