問題のコード

元々書いていたコードは前述の問題を解くためのものだが、この記事に載せるにあたって該当部分だけを抜き出して適宜変更した。したがって、元の問題とは殆ど無関係なものになっている。

def lower_func(v):
    w = match[v]
    if(w < 0):
        match[v] = v+1
        print("lower_func:" , match)
    return True

def higher_func():
    match = [-1] * V
    for v in range(V):
        lower_func(v)
        print("higher_func:", match)
    return 

V = 3
match = [-1] * V

higher_func()
print("global:", match)

グローバル部分でmatchというリストを定義し、higher_func()を呼ぶ。
higher_func()の中では、matchを同じ値でもう一度初期化しておいてから、lower_func()を呼ぶ。
lower_func()の中で順次値を書き換える。

#出力
lower_func: [1, -1, -1]
higher_func: [-1, -1, -1]
lower_func: [1, 2, -1]
higher_func: [-1, -1, -1]
lower_func: [1, 2, 3]
higher_func: [-1, -1, -1]
global: [1, 2, 3]

……あれれ。
globalとlower_funcの中は書き換わっているのに、higher_funcの中のmatchは書き換わっていない！
どうなってるの。

idを見てみよう

こういう問題（同じ名前の変数がどのオブジェクトを指しているのか分かりにくい問題）の場合、idを見ると分かりやすいだろう。

def lower_func(v):
    w = match[v]
    if(w < 0):
        match[v] = v+1
        print("lower_func:", match)
        print("lower_func:", id(match))
    return True

def higher_func():
    match = [-1] * V
    for v in range(V):
        lower_func(v)
        print("higher_func:", match)
        print("higher_func:", id(match))
    return 

V = 3
match = [-1] * V

higher_func()
print("global:", match)
print("global:", id(match))

# 出力（注意：idは実行するごとに異なる値となる）
lower_func: [1, -1, -1]
lower_func: 33907336
higher_func: [-1, -1, -1]
higher_func: 39538248
(中略)
global: [1, 2, 3]
global: 33907336

複数回呼び出されるので複数回idがprintされるわけだが、全部書いても意味がないので略した。

なるほど、lower_func()とグローバル領域のmatchは同じオブジェクトを指している。つまり、グローバル変数だ。
そして、higher_func()のmatchは関数内のローカル変数だ。
lower_func()はグローバル変数を書き換えているが、higher_func()内で出力しているのは別の変数の値なので、出力された値は変わらない。

一件落着……したようだが、まだ疑問がある。

疑問その1

pythonの公式ドキュメントより引用。

関数内で変数への代入を行うと、その値はすべてこのローカルなシンボルテーブルに記憶されます。一方、変数の参照を行うと、まずローカルなシンボルテーブルが検索され、次にさらに外側の関数のローカルなシンボルテーブルを検索し、その後グローバルなシンボルテーブルを調べ、最後に組み込みの名前テーブルを調べます。
4. その他の制御フローツール — Python 3.7.3 ドキュメント

lower_func()では w = match[v]で、変数の参照を行っている。「ローカルなシンボルテーブルが検索され、次にさらに外側の関数のローカルなシンボルテーブルを検索し……」とチュートリアルには書いてある。
つまり、最初にlower_func()の中を検索する。そこにmatchという変数は定義されていない。
したがって、次に呼び出し元であるhigher_func()を検索する。そこにmatchという変数は定義されて……いるじゃん。
あれ? チュートリアルのドキュメントの通りなら、lower_func()の中でmatchを参照したらhigher_func()の中のmatchになるんじゃないの?

疑問その2

公式ドキュメントの、先ほどの箇所にはこうも書いてある。「関数内で変数への代入を行うと、その値はすべてこのローカルなシンボルテーブルに記憶されます。」

match[v] = v+1の部分で代入を行っている。そしたらmatchはローカルになるんじゃないの?

従って、関数の中では、グローバルな変数を参照することはできますが、直接値を代入することは (global 文で名前を挙げておかない限り)できません。
4. その他の制御フローツール — Python 3.7.3 ドキュメント

同じことを別の言い方をすると、なんで関数内でグローバル変数に値を代入できているの?
この記事を見ていると、関数内でグローバル変数に値を代入するとエラーが発生するようだけど。
Pythonの変数スコープの話 - Qiita

（多分、疑問1・2とも、変数matchそのものではなくmatchの要素に対して参照・代入を実行しているところがミソな予感がする。が、これ以上は調べてもよくわからないので撤退する）

疑問は措いておいてひとまず解決するなら

global文を使えば、その変数がグローバル領域のものであることを明示できる。
関数を定義した直後にglobal matchと書いて、matchがグローバル変数であることを書けば良い。

def lower_func(v):
    global match #追加
    w = match[v]
    if(w < 0):
        match[v] = v+1
        print("lower_func:", match)
        print("lower_func:", id(match))
    return True

def higher_func():
    global match #追加
    match = [-1] * V
    for v in range(V):
        lower_func(v)
        print("higher_func:", match)
        print("higher_func:", id(match))
    return 

V = 3
match = [-1] * V

higher_func()
print("global:", match)
print("global:", id(match))

# 出力（注意：idは実行するごとに異なる値となる）
lower_func: [1, -1, -1]
lower_func: 39406536
higher_func: [1, -1, -1]
higher_func: 39406536
lower_func: [1, 2, -1]
lower_func: 39406536
higher_func: [1, 2, -1]
higher_func: 39406536
lower_func: [1, 2, 3]
lower_func: 39406536
higher_func: [1, 2, 3]
higher_func: 39406536
global: [1, 2, 3]
global: 39406536