はじめに
再帰関数は便利な反面、欠点も抱えています。
そのため以前から再帰関数を非再帰関数に変換することがありました。
変換自体は出来ていたのですが、行き当たりばったりで何故そう変換出来るのか理論的に考えていませんでした。
一度しっかりと変換の過程を理論的に考えみたいと思いながらも機会が取れずにいました。
そんな中で、再帰関数の記事がトレンドに上がっていた事があり記事を書き始めました。
(ほったらかしにしていたので大分時間がたってしまいましたが)
別のプログラムを書いていて今更ながらスタックの重要性に気がついたのも要因です。
もっとも、再帰関数の有用性を否定するものではありません。
筆者は、再帰関数が大好きです。
想定読者
プログラム言語は、何でも良いので Python を使うことにします。
再帰プログラムを作るのに使用したアルゴリズム自体の説明はしません。
そのため、Python が分かりアルゴリズムも分かる(調べられる)方を対象と考えています。
コールスタックとスタック
プログラムの実行を制御する方のスタックを、コールスタック(Call Statck)と呼びます。
実行スタック(Execution Stack)、制御スタック(Control Stack)、関数スタック(Function Stack)などと呼ばれる事もあります。
この記事では、コールスタックで統一します。
また、データ構造としてのスタックを単にスタック(Stack)と呼ぶ事にします。
なぜ再帰関数が避けられるのか
再帰関数は、関数呼び出しによりコールスタックを使用します。
コールスタックに格納できる容量には上限があります。
コンパイラ等の設定を変更することで容量を変更できますが有限なのは変わりません。
(最近、触っていなのでどの程度融通が利くのか分かりませんが。)
コールスタックの容量を超えると、スタックオーバーフロー(stack overflow)を起こしプログラムの実行が停止します。
再帰関数は、その原理上コールスタックを大量に消費しやすくスタックオーバーフローの原因となりがちです。
設定次第ではありますが、それほど多くない筆者の経験上、コールスタックを使いつぶしてスタックオーバーフローを起こすのは簡単です。
(おまえの糞プログラムのせいだと突っ込まれるかもしれませんが)
そのため、避けられる傾向があります。
一方、スタックが使うヒープ領域は、コールスタックよりも比較的融通が利くものです。
(これも設定次第でなおかつ作るプログラム次第ではあると思いますが)
そのため、スタックの使用へと切り替えていこうという訳です。
最近は、末尾再帰最適化といって末尾再帰をループ構造に変換してくれる機能をもったコンパイラ等があります。
それほど気にしなくても良くなってきてはいます。
便利になってきたものです。
変換方針
この記事では、典型的な変換方法と思いますが、再帰関数をスタックを使って非再帰関数にするのを考えていきたいと思います。
コールスタックの使用をスタックの使用に切り替えるイメージです。
階乗
まずは、単純な階乗を例に考えてみます。
階乗 再帰版
階乗を再帰を使って実装すると以下のようなものになります。
def factorialR(n) :
if n == 0 :
return 1
return n * factorialR(n-1)
階乗 再帰版 コールスタックの動き
n=5 としてこの関数を実行した場合のコールスタックの様子を図示してみます。
厳密な動作ではなくイメージとしての動きです。
関数が実行されるとまずその呼び出し自身factorialR(5)をコールスタックに Push します。
factorialR(5)は、実行されると5 * factorialR(4)に変換されます。
そして、factorialR(4)を呼び出しコールスタックに Push します。
factorialR(4)は、実行されると4 * factorialR(3)に変換されます。
| Bottom |
Top |
| 5 * f(4) |
4 * f(3) |
以下、同じように動作します。
| Bottom |
|
Top |
| 5 * f(4) |
4 * f(3) |
f(3) |
| Bottom |
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
| Bottom |
|
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
f(2) |
| Bottom |
|
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
2 * f(1) |
| Bottom |
|
|
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
2 * f(1) |
f(1) |
| Bottom |
|
|
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
2 * f(1) |
1 * f(0) |
再帰呼び出しが続き、n=0 まで来ました。
| Bottom |
|
|
|
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
2 * f(1) |
1 * f(0) |
f(0) |
n=0 の場合は、1 が返されます。
| Bottom |
|
|
|
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
2 * f(1) |
1 * f(0) |
1 |
factorialR(0)が実行され 1 が返されることにより、コールスタックが 1 つ下がります。
そして、n=1 の呼び出し時点に戻り 1 * factorialR(0)が解決されて1 * 1 = 1が返されます。
| Bottom |
|
|
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
2 * f(1) |
1 |
同じように前の実行結果が返されたことにより、コールスタックが 1 つ下がります。
n=2 の呼び出し時点に戻り 2 * factorialR(1)が解決されて 2 * 1 = 2が返されます。
以下、同じように動作します。
| Bottom |
|
|
Top |
| 5 * f(4) |
4 * f(3) |
3 * f(2) |
2 |
| Bottom |
|
Top |
| 5 * f(4) |
4 * f(3) |
6 |
最終的に5 * factorialR(4) = 5 * 24 = 120となり 120 が返されます。
再帰版の階乗は、関数の呼び出しを再帰的に行っているので呼び出しがコールスタックに積まれてしまいます。
関数の構造をそのままにコールスタックを使用しないようにしたいです。
上記の関数は、階乗を計算するに途中の計算結果と次の関数呼び出しに使っていた引数が必要でした。
そこで途中の計算結果を 1 つの変数に、次の関数呼び出しに使われていた値をスタックに積むようにしてみます。
5 * f(4)の場合は、5 を変数へ、4 をスタックに積むことになります。
この考えを元に、非再帰版を作ってみたいと思います。
階乗 非再帰版
こちらも、n=5 の場合のスタックの動きを図示してみます。
関数が始まると最初に 5 をスタックに Push します。
また、途中の計算結果を保存する変数 Result を 1 にしておきます。
次の段階では、スタックを pop させて値 5 を取り出します。
そして、取り出した値を Result に掛けます。
最後に、5-1=4の値 4 をスタックに push します。
次の段階では、スタックを pop させて値 4 を取り出します。
そして、取り出した値を Result に掛けます。
最後に、5-1=3の値 3 をスタックに push します。
以下、同じように動作します。
値 0 を pop させたら、1 を Result に掛けます。
0 の場合は、次にスタックに push する値はありません。
スタックがなくなったので Result の値 120 が n=5 の階乗の答えとして求められます。
階乗が単純なためにスタックを使う意味が見い出せないかと思います。
しかし、変換の一般化のためにこのようにしています。
これを元に関数にしてみます。
愚直に表すならば以下のようになるでしょうか。
def factorialL(n):
stack = [n]
result = 1
current = 0
while len(stack) > 0:
current = stack.pop()
if current <= 0:
current = 1
else :
stack.append(current - 1)
result *= current
return result
階乗 非再帰版 その 2
再帰版のコールスタックの動きをスタックで再現してみる実装も考えてみます。
スタックの動きを以下のようにしてみます。
n=0 まで来ると0!=1なので 1 が確定します。
そして確定した 1 を pop させ、スタックを 1 つ崩します。
この pop させた 1 は、Result として保存しておきます。
| Bottom |
|
|
|
Top |
Result |
| 5 |
4 |
3 |
2 |
1 |
1 |
次に Top の値 1 を pop させ、スタックを 1 つ崩します。
先ほど保存した 1 と今 pop させた 1 を使い1 * 1を計算し、1を Result として保存します。
これにより n=1 の値が確定しました。
以下、同じように実行させていきます。
| Bottom |
|
|
Top |
Result |
| 5 |
4 |
3 |
2 |
1 |
Top の値 2 を pop させて Result の値 1 と掛けて結果 2 を Result に入れる。
| Bottom |
|
Top |
Result |
| 5 |
4 |
3 |
2 |
Top の値 3 を pop させて Result の値 2 と掛けて結果 6 を Result に入れる。
Top の値 4 を pop させて Result の値 6 と掛けて結果 24 を Result に入れる。
Top の値 5 を pop させて Result の値 24 と掛けて結果 120 を Result に入れる。
スタックがなくなったので Result の値 120 が n=5 の階乗の答えとして求められます。
こちらの場合は、以下のようになるでしょうか。
def factorialL(n):
stack = []
for i in range(n, 0, -1) :
stack.append(i)
result = 1
for i in range(len(stack)) :
top = stack.pop()
result *= top
return result
階乗 非再帰版 単純化
もう少しすっきりした実装は以下のようになります。
def factorial1(n):
result = 1
for i in range(1, n + 1) :
result *= i
return result
from functools import reduce
def factorial2(n):
return reduce(lambda a, b: a * b, range(1, n + 1), 1)
フィボナッチ数列
次は、フィボナッチ数列を例に取ってみたいと思ます。
フィボナッチ数列 再帰版
フィボナッチ数列の再帰を使った典型的な実装は、以下のようになると思います。
階乗との大きな違いは、1 度の実行で自分自身を 2 回呼び出していることです。
def fibonacciR(n) :
if n == 0 or n == 1 :
return n
return fibonacciR(n - 2) + fibonacciR(n - 1)
フィボナッチ数列 再帰版 コールスタックの動き
階乗と同じように n=5 の場合のコールスタックの様子を図示してみます。
関数が実行されるとまずfibonacciR(5)がコールスタックに Push されます。
そしてfibonacciR(3) + fibonacciR(4)に変換されます。
次に、fibonacciR(3)が呼び出されコールスタックに Push されます。
実行されるとfibonacciR(1) + fibonacciR(2)に変換されます。
| Bottom |
Top |
| f(3) + f(4) |
f(3) |
| Bottom |
Top |
| f(3) + f(4) |
f(1) + f(2) |
次に、fibonacciR(1)が呼び出されコールスタックに Push されます。
fibonacciR(1)は、実行されると 1 が返されます。
これにより、fibonacciR(3)呼び出し時のfibonacciR(1) + fibonacciR(2)が一部解決されて1 + fibonacciR(2)となります。
| Bottom |
|
Top |
| f(3) + f(4) |
f(1) + f(2) |
f(1) |
| Bottom |
|
Top |
| f(3) + f(4) |
f(1) + f(2) |
1 |
| Bottom |
Top |
| f(3) + f(4) |
1 + f(2) |
fibonacciR(2)を解決するために、それが呼び出されコールスタックに Push されます。
実行されるとfibonacciR(0) + fibonacciR(1)に変換されます。
| Bottom |
|
Top |
| f(3) + f(4) |
1 + f(2) |
f(2) |
| Bottom |
|
Top |
| f(3) + f(4) |
1 + f(2) |
f(0) + f(1) |
fibonacciR(0)が呼び出されコールスタックに Push されます。
fibonacciR(0)は、実行されると 0 が返されます。
これにより、fibonacciR(2)呼び出し時のfibonacciR(0) + fibonacciR(1)が一部解決されて0 + fibonacciR(1)となります。
| Bottom |
|
|
Top |
| f(3) + f(4) |
1 + f(2) |
f(0) + f(1) |
f(0) |
| Bottom |
|
|
Top |
| f(3) + f(4) |
1 + f(2) |
f(0) + f(1) |
0 |
| Bottom |
|
Top |
| f(3) + f(4) |
1 + f(2) |
0 + f(1) |
同じように、fibonacciR(1)が呼び出されコールスタックに Push されます。
fibonacciR(1)は、実行されると 1 が返されます。
これにより、fibonacciR(2)呼び出し時の0 + fibonacciR(1)が解決されて0 + 1 = 1となります。
| Bottom |
|
|
Top |
| f(3) + f(4) |
1 + f(2) |
0 + f(1) |
f(1) |
| Bottom |
|
|
Top |
| f(3) + f(4) |
1 + f(2) |
0 + f(1) |
1 |
| Bottom |
|
Top |
| f(3) + f(4) |
1 + f(2) |
0 + 1 |
fibonacciR(3)呼び出し時の1 + fibonacciR(1)が解決されて1 + 1 = 2となります。
| Bottom |
Top |
| f(3) + f(4) |
1 + 1 |
fibonacciR(5)呼び出し時のfibonacciR(3) + fibonacciR(4)の一部が解決されて2 + fibonacciR(4)となります。
以下同じように動作します。
| Bottom |
Top |
| 2 + f(4) |
f(2) + f(3) |
| Bottom |
|
Top |
| 2 + f(4) |
f(2) + f(3) |
f(2) |
| Bottom |
|
Top |
| 2 + f(4) |
f(2) + f(3) |
f(1) + f(0) |
| Bottom |
|
|
Top |
| 2 + f(4) |
f(2) + f(3) |
f(1) + f(0) |
f(1) |
| Bottom |
|
|
Top |
| 2 + f(4) |
f(2) + f(3) |
f(1) + f(0) |
1 |
| Bottom |
|
|
Top |
| 2 + f(4) |
f(2) + f(3) |
1 + f(0) |
f(0) |
| Bottom |
|
|
Top |
| 2 + f(4) |
f(2) + f(3) |
1 + f(0) |
0 |
| Bottom |
|
Top |
| 2 + f(4) |
f(2) + f(3) |
1 |
| Bottom |
Top |
| 2 + f(4) |
1 + f(3) |
| Bottom |
|
Top |
| 2 + f(4) |
1 + f(3) |
f(3) |
| Bottom |
|
Top |
| 2 + f(4) |
1 + f(3) |
f(1) + f(2) |
| Bottom |
|
|
Top |
| 2 + f(4) |
1 + f(3) |
f(1) + f(2) |
f(1) |
| Bottom |
|
|
Top |
| 2 + f(4) |
1 + f(3) |
f(1) + f(2) |
1 |
| Bottom |
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
| Bottom |
|
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
f(2) |
| Bottom |
|
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
f(0) + f(1) |
| Bottom |
|
|
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
f(0) + f(1) |
f(0) |
| Bottom |
|
|
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
f(0) + f(1) |
0 |
| Bottom |
|
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
0 + f(1) |
| Bottom |
|
|
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
0 + f(1) |
f(1) |
| Bottom |
|
|
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
0 + f(1) |
1 |
| Bottom |
|
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + f(2) |
0 + 1 |
| Bottom |
|
Top |
| 2 + f(4) |
1 + f(3) |
1 + 1 |
| Bottom |
Top |
| 2 + f(4) |
1 + 2 |
以上のように動作し、n=5 の時の値 5 が返されます。
長々と記述しましたが、コールスタックの動きとしてはこのようになります。
これだけでは分かりづらいので、このコールスタックの動きを 2 分木を使って表したいと思います。
フィボナッチ数列再帰版の 2 分木
2 分木で表してみると、以下のようになります。
graph TB;
0[5]---1[3]
0---2[4]
1---3[1]
1---4[2]
4---5[0]
4---6[1]
2---7[2]
2---8[3]
7---9[0]
7---10[1]
8---11[1]
8---12[2]
12---13[0]
12---14[1]
丁度コールスタックの深さが 2 分木の深さに対応しているのが分かります。
また、値が解決する順番が 2 分木の深さ優先探索の探索順に対応しているのが分かります。
2 分木の深さ優先探索は、スタックを使って実装されるとよく説明されます。
ここでは、コールスタックを使って実装した形になりました。
さて次に非再帰版を作ってみたいと思います。
フィボナッチ数列 非再帰版
フィボナッチ数列の再帰版も簡素な関数で途中の計算結果と言えるものがありません。
そこで何をスタックに積んでいくかと言うと関数に渡される引数をスタックに積んでいくことにします。
今までと同じように n=5 の場合のスタックの様子を図示してみます。
実行を開始すると最初に与えられた引数 5 をスタックに Push します。
次の段階では、スタックを Pop して 5 を取り出します。
5 は、フィボナッチ数列の漸化式から値を確定できないです。
代わりに、n-2とn-1を求める事にします。
つまり、5-2=3と5-1=4をそれぞれスタックに Push していきます。
大きい数から先に Push していく事にします。
次の段階では、スタックを Pop して 3 を取り出します。
3 は、値を確定できないので、代わりに 1, 2 をそれぞれ Push します。
次の段階では、スタックを Pop して 1 を取り出します。
1 は、値として確定できるので Result として保存します。
次の段階では、スタックを Pop して 2 を取り出します。
2 は、値を確定できないので、代わりに 0, 1 をそれぞれ Push します。
| Bottom |
|
Top |
Result |
| 4 |
1 |
0 |
1 |
次の段階では、スタックを Pop して 0 を取り出します。
0 は、値として確定できるので、Result に足し合わせて保存します。
次の段階では、スタックを Pop して 1 を取り出します。
1 は、値として確定できるので、Result に足し合わせて保存します。
以下、同じように動作します。
| Bottom |
|
Top |
Result |
| 3 |
1 |
0 |
2 |
以上のように動作し、こちらも n=5 の時の値 5 が返されます。
これを再び愚直に実装してみたいと思います。
def fibonacciL(n) :
result = 0
current = 0
stack = [n]
while len(stack) > 0 :
current = stack.pop()
if current == 1 or current == 0 :
result += current
else :
stack.append(current-1)
stack.append(current-2)
return result
階乗と似たような実装に落ち着きました。
(似たような実装にしようとしてはいますが)
フィボナッチ数列 非再帰版 単純化
スタックを意識せずに答えだけを求めるならば以下のようにも出来ます。
スタックの場合は、n -> n-1 -> n-2-> ... -> 0のように漸化式の係数が大きい方から求めていました。
こちらは、0 -> 1 -> ... -> nのように係数の小さい方から求めています。
def fibonacciL2(n):
if n == 0:
return 0
x, y = 0, 1
for _ in range(n - 1):
x, y = y, x + y
return y
クイックソート
次にクイックソートも考えてみます。
クイックソート 再帰版
クイックソートを、以下のように再帰で実装してみました。
重複した値も取れるようにしています。
典型的な実装とは多少の差異があるかとは思いますが、クイックソートになっていると思います。
ソートの過程を表示するためにprint()を入れています。
また、そのための補助的な関数を定義して使っています。
isSorted()は、ソートされているか判定するものです。
def isSorted(lt):
b = lt[0]
for x in lt:
if b > x:
return False
b = x
return True
def getListIndeces(lt, s=0):
if len(lt) == 0:
return "><"
maxLen = len(str(max(lt)))
text = reduce(lambda x, y: x + y, [f"{i+s:{maxLen}}, " for i, x in enumerate(lt)], ">")
return f"{text[:-2]}<"
def listToFormatedString(lt):
if len(lt) == 0:
return "[]"
maxLen = len(str(max(lt)))
text = reduce(lambda x, y: x + y, [f"{x:{maxLen}}, " for x in lt], "[")
return f"{text[:-2]}]"
def getPivot(lt, l, r):
return lt[l + int((r - l) / 2)]
def quickSort(lt):
_quickSort(lt, 0, len(lt) - 1)
def _quickSort(lt, l, r):
if l >= r:
print(f" {getListIndeces(lt[l:r+1], s=l)}, l: {l}, r: {r}\nr: {listToFormatedString(lt[l:r+1])}")
return
i = l
j = r
p = getPivot(lt, l, r)
print(f" {getListIndeces(lt[l:r+1], s=l)}, l: {l}, r: {r}, p: {p}\ns: {listToFormatedString(lt[l:r+1])}")
while i < j:
while lt[i] < p:
i += 1
while lt[j] > p:
j -= 1
if i < j:
if lt[i] == lt[j]:
j -= 1
else:
lt[i], lt[j] = lt[j], lt[i]
print(f"p: {listToFormatedString(lt[l:r+1])}, {i}: {lt[j]}, {j}: {lt[i]}")
_quickSort(lt, l, i - 1)
_quickSort(lt, j + 1, r)
引数に[7, 2, 1, 4, 6, 0, 8, 5, 9, 3]を与えて実行してみます。
lt = [7, 2, 1, 4, 6, 0, 8, 5, 9, 3]
quickSort(lt)
print(lt, isSorted(lt))
そうすると以下のような実行結果が表示されます。
>0, 1, 2, 3, 4, 5, 6, 7, 8, 9<, l: 0, r: 9, p: 6
s: [7, 2, 1, 4, 6, 0, 8, 5, 9, 3]
p: [3, 2, 1, 4, 6, 0, 8, 5, 9, 7], 0: 7, 9: 3
p: [3, 2, 1, 4, 5, 0, 8, 6, 9, 7], 4: 6, 7: 5
p: [3, 2, 1, 4, 5, 0, 6, 8, 9, 7], 6: 8, 7: 6
p: [3, 2, 1, 4, 5, 0, 6, 8, 9, 7], 6: 6, 6: 6
>0, 1, 2, 3, 4, 5<, l: 0, r: 5, p: 1
s: [3, 2, 1, 4, 5, 0]
p: [0, 2, 1, 4, 5, 3], 0: 3, 5: 0
p: [0, 1, 2, 4, 5, 3], 1: 2, 2: 1
p: [0, 1, 2, 4, 5, 3], 1: 1, 1: 1
r: >0<, l: 0, r: 0
r: [0]
>2, 3, 4, 5<, l: 2, r: 5, p: 4
s: [2, 4, 5, 3]
p: [2, 3, 5, 4], 3: 4, 5: 3
p: [2, 3, 4, 5], 4: 5, 5: 4
p: [2, 3, 4, 5], 4: 4, 4: 4
>2, 3<, l: 2, r: 3, p: 2
s: [2, 3]
p: [2, 3], 2: 2, 2: 2
r: ><, l: 2, r: 1
r: []
r: >3<, l: 3, r: 3
r: [3]
r: >5<, l: 5, r: 5
r: [5]
>7, 8, 9<, l: 7, r: 9, p: 9
s: [8, 9, 7]
p: [8, 7, 9], 8: 9, 9: 7
p: [8, 7, 9], 9: 9, 9: 9
>7, 8<, l: 7, r: 8, p: 8
s: [8, 7]
p: [7, 8], 7: 8, 8: 7
p: [7, 8], 8: 8, 8: 8
r: >7<, l: 7, r: 7
r: [7]
r: ><, l: 9, r: 8
r: []
r: ><, l: 10, r: 9
r: []
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] True
クイックソート 再帰版 コールスタックの動き
クイックソートもコールスタックの動きを図示して行きます。
まずはf(lt)としてコールスタックに Push されます。
初めにピボットとして 6 が選択され、6 未満の値がリストの前へ、6 より大きい値がリストの後へ移動されます。
選り分けた結果、境目のインデックスが 6 なのでlt[0:6]と、lt[7:10]でそれぞれquickSort()が実行されます。
境目のインデックスの値は、ピボットになります。
重複した値がある場合、ピボットとして選択された値が選り分けられたリストに存在する可能性があります。
境目のインデックスは、ソート済みとなり位置が確定されます。
位置が確定した要素は、Resultと表示することにします。
| Bottom Top |
Result |
f(lt[7:10]), f(lt[0:6])
|
lt[6] |
次に実行のためにコールスタックにf(lt[0:6])が Push されます。
| Bottom |
Top |
Result |
f(lt[7:10]) |
f(lt[0:6]) |
lt[6] |
ここでは、ピボットとして 1 が選ばれ、1 未満が前へ、 1 より大きい値が後ろへ分けられます。
区切りのインデックスが 1 となり、lt[0:1]と、lt[2:6]でそれぞれquickSort()が実行されます。
| Bottom |
Top |
Result |
f(lt[7:10]) |
f(lt[2:6]), f(lt[0:1])
|
lt[1] + lt[6]
|
コールスタックにf(lt[0:1])が Push されます。
| Bottom |
|
Top |
Result |
f(lt[7:10]) |
f(lt[2:6]) |
f(lt[0:1]) |
lt[1] + lt[6]
|
lt[0:1]は、長さが 1 なので位置を確定し、コールスタックから Pop されます。
| Bottom |
Top |
Result |
f(lt[7:10]) |
f(lt[2:6]) |
lt[0:2] + lt[6]
|
コールスタックが戻って、次にlt[2:6]の範囲がソートされます。
ここでは、ピボットとして 4 が選ばれ、4 未満の値と 4 より大きい値の範囲に分けられます。
区切りのインデックスが 4 となり、lt[2:4]と、lt[5:6]でそれぞれquickSort()が実行されます。
lt[4]の位置を確定させます。
| Bottom |
Top |
Result |
f(lt[7:10]) |
f(lt[5:6]), f(lt[2:4]), |
lt[0:2] + lt[4]+ lt[6]
|
コールスタックにf(lt[2:4])が Push されます。
| Bottom |
|
Top |
Result |
f(lt[7:10]) |
f(lt[5:6]) |
f(lt[2:4]) |
lt[0:2] + lt[4]+ lt[6]
|
ピボットとして 2 が選ばれ、2 未満と 2 より大きい範囲に分けられます。
区切りのインデックス 2 で分けられ lt[2:2]とlt[3:4]でそれぞれquickSort()が実行されます。
lt[2]を確定されます。
| Bottom |
|
Top |
Result |
f(lt[7:10]) |
f(lt[5:6]) |
f(lt[3:4]), f(lt[2:2])
|
lt[0:3] + lt[4] + lt[6]
|
lt[2:2]もlt[3:4]も実行されますが範囲の長さが 1 以下 なので位置が確定します。
f(lt[2:2]) が Push され、長さが 0 なので Pop される。
f(lt[3:4]) が 実行され、lt[3]の位置が確定し、 Pop される。
| Bottom |
Top |
Result |
f(lt[7:10]) |
f(lt[5:6]) |
lt[0:3] + lt[4] + lt[6]
|
コールスタックが戻って、次にlt[5:6]の範囲がソートされます。
lt[5:6]も範囲が 1 なので位置が確定し、Pop されます。
これでリストの前半部分がソートされ確定されました。
後半部分も同じように処理されます。
| Bottom Top |
Result |
f(lt[7:10]) |
lt[0:7] |
ピボットとして 9 が選ばれ、lt[7:9]とlt[9:9]に分けられる。
lt[9]が確定する。
| Bottom Top |
Result |
f(lt[9:9]), f(lt[7:9])
|
lt[0:7] + lt[9]
|
f(lt[7:9])が Push される。
| Bottom |
Top |
Result |
f(lt[9:9]) |
f(lt[7:9]) |
lt[0:7] + lt[9]
|
ピボットとして 8 が選ばれ、lt[7:8]とlt[8:8]に分けられる。
lt[8]が確定する。
| Bottom |
Top |
Result |
f(lt[9:9]) |
f(lt[8:8]), f(lt[7:8])
|
lt[0:7] + lt[8:10]
|
f(lt[7:8])が Push される。
| Bottom |
|
Top |
Result |
f(lt[9:9]) |
f(lt[8:8]) |
f(lt[7:8]) |
lt[0:7] + lt[8:10]
|
lt[7]の位置が確定する。
| Bottom |
Top |
Result |
f(lt[9:9]) |
f(lt[8:8]) |
lt |
lt[8:8]もlt[9:9]も長さが 0 なので何もせずに終了して処理が終わる。
フィボナッチ数列のコールスタックの動きと同じようになったのが分かります。
クイックソート 非再帰版
クイックソートも非再帰に変換していきます。
今までの考え方と同じようにコールスタックに積まれていく途中経過をスタックに積んでいく形になります。
クイックソートの場合は、次にソートしなければならない範囲をスタックに積んでいく事になります。
実装は、以下のようになりました。
苦労するかと思っていましたが、再帰版とほとんど変わらない形になりました。
def quickSortL(lt):
length = len(lt)
stack = [(0, length - 1)]
while len(stack) > 0:
l, r = stack.pop()
if l >= r:
continue
i = l
j = r
p = getPivot(lt, l, r)
while i < j:
while lt[i] < p:
i += 1
while lt[j] > p:
j -= 1
if i < j:
if lt[i] == lt[j]:
j -= 1
else:
lt[i], lt[j] = lt[j], lt[i]
stack.append((j + 1, r))
stack.append((l, i - 1))
2 分探索
ここまで来ると蛇足ですが、2 分探索も考えてみたいと思います。
2 分探索 再帰版
まずは、再帰版ですが、以下のように実装しました。
これは、値が重複しないソートされたリストが渡されるのを前提としています。
uniqueSorted()を使えば条件を満たすリストに出来ます。
これも説明のためにprint()を入れています。
def uniqueSorted(lt):
return sorted(list(set(lt)))
def binarySearchR(lt, n):
return _binarySearchR(lt, n, 0, len(lt) - 1)
def _binarySearchR(lt, n, l, r):
if l > r:
return -1
middleIndex = int(l + (r - l) / 2)
middleValue = lt[middleIndex]
print(getListIndeces(lt[l:r + 1], l))
print(listToFormatedString(lt[l:r + 1]), middleIndex, middleValue)
if middleValue > n:
return _binarySearchR(lt, n, l, middleIndex - 1)
elif middleValue < n:
return _binarySearchR(lt, n, middleIndex + 1, r)
else:
return middleIndex
以下のように、実行しました。
lt = [3, 6, 12, 13, 14, 16, 17, 22, 51, 56, 58, 62, 66, 70, 74, 75, 80, 92, 94, 95]
n = 70
print(binarySearchR(lt, n))
そうすると、以下の実行結果が得られます。
> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19<
[ 3, 6, 12, 13, 14, 16, 17, 22, 51, 56, 58, 62, 66, 70, 74, 75, 80, 92, 94, 95] 9 56
>10, 11, 12, 13, 14, 15, 16, 17, 18, 19<
[58, 62, 66, 70, 74, 75, 80, 92, 94, 95] 14 74
>10, 11, 12, 13<
[58, 62, 66, 70] 11 62
>12, 13<
[66, 70] 12 66
>13<
[70] 13 70
13
2 分探索 再帰版 コールスタックの動き
コールスタックを図示します。
まずは、リストとしてlt、探したい数nを 70 としてコールスタックに Push されます。
中央値のインデックスとして 9 が選ばれます。
lt[9]の値は、56 なので求めたい数 70 より小さいです。
そのためリストの後半部分の探索を進める事になります。
リストの後半部分の探索の為に、lt[10:20]としてbinarySearch()が実行されます。
f(lt[10:20])が Push されます。
中央値のインデックスとして 14 が選ばれます。
lt[14]の値は、74 なので求めたい数 70 より大きいです。
そのためリストの前半部分の探索を進める事になります。
| Bottom |
Top |
f(lt) |
f(lt[10:20]) |
探索を進める為に、lt[10:14]としてbinarySearch()が実行されます。
f(lt[10:14])が Push されます。
インデックス 11 が選ばれます。
lt[11]の値は、62 なので求めたい数 70 より小さいです。
そのためリストの後半部分の探索を進める事になります。
| Bottom |
|
Top |
f(lt) |
f(lt[10:20]) |
f(lt[10:14]) |
探索を進める為に、lt[12:14]としてbinarySearch()が実行されます。
f(lt[12:14])が Push されます。
インデックス 12 が選ばれます。
lt[12]の値は、66 なので求めたい数 70 より小さいです。
そのためリストの後半部分の探索を進める事になります。
| Bottom |
|
|
Top |
f(lt) |
f(lt[10:20]) |
f(lt[10:14]) |
f(lt[12:14]) |
探索を進める為に、lt[13:14]としてbinarySearch()が実行されます。
f(lt[13:14])が Push されます。
インデックス 13 が選ばれます。
lt[13]の値は、70 なので求めたい数 70 と等しいです。
等しい数が見つかったので、インデックスの値 13 を返します。
| Bottom |
|
|
|
Top |
f(lt) |
f(lt[10:20]) |
f(lt[10:14]) |
f(lt[12:14]) |
f(lt[13:14]) |
以下、値を返すつつ、コールスタックから Pop されます。
| Bottom |
|
|
|
Top |
f(lt) |
f(lt[10:20]) |
f(lt[10:14]) |
f(lt[12:14]) |
13 |
| Bottom |
|
|
Top |
f(lt) |
f(lt[10:20]) |
f(lt[10:14]) |
13 |
| Bottom |
|
Top |
f(lt) |
f(lt[10:20]) |
13 |
コールスタックの動きが階乗と同じになりました。
条件分岐の違いや返された値で処理を行うかどうか以外は、ほとんど同じ構造をしていると言えると思います。
2 分探索 非再帰版
非再帰版は、以下のようになりました。
こちらもクイックソートと同じで、再帰版とほとんど同じ構造に出来ました。
def binarySearchL(lt, n):
stack = [(0, len(lt) - 1)]
while len(stack) > 0:
l, r = stack.pop()
if l > r:
return -1
middleIndex = int(l + (r - l) / 2)
middleValue = lt[middleIndex]
if middleValue > n:
stack.append((l, middleIndex - 1))
elif middleValue < n:
stack.append((middleIndex + 1, r))
else:
return middleIndex
2 分探索の場合は、コールスタックが増減を繰り返さない単純な動きでしたのでスタックを使わなくて簡単に変換出来ます。
多少シンプルにしたものが以下になります。
def binarySearchL2(lt, n):
l, r = 0, len(lt) - 1
while l <= r:
middleIndex = int(l + (r - l) / 2)
middleValue = lt[middleIndex]
if middleValue > n:
l, r = l, middleIndex - 1
elif middleValue < n:
l, r = middleIndex + 1, r
else:
return middleIndex
return -1
最後に
単純なアルゴリズムしか挙げていないのもありますが、どの再帰関数もコールスタックの動きは、同じようなものになります。
つまり同じような構造で実装できると言えると思います。
結局、再帰関数の構造をしっかり理解できていないから非再帰関数への変換に苦労していたのだと思いました。
大きな違いは、コールスタックを利用するのかスタックを利用するのかぐらいのものです。
そして、学校などで習う基本的なデータ構造とアルゴリズムの大切さが身に染みて分かりました。
基本は大事ですね。
不真面目だった学生時代のツケが回ってきたという事でしょうか(´・ω・`)
付録
コールスタックの深さを確認/変更する。
pythonのコールスタックの深さは、sys.getrecursionlimit()で確認できます。
環境依存ですが、sys.setrecursionlimit(limit)で深さを変更できます。
2 分木の mermaid
graph TB;
0[5]---1[3]
0---2[4]
1---3[1]
1---4[2]
4---5[0]
4---6[1]
2---7[2]
2---8[3]
7---9[0]
7---10[1]
8---11[1]
8---12[2]
12---13[0]
12---14[1]
