目次
サンプル・プログラム
1から10の和を求める数式
「2.2 繰り返し処理」で紹介した1から10の和を求める計算だが、これを数学で表すとどうなるだろうか。
\[ 1+2+...+10 = k_{1} + k_{2} + ... k_{10} = \displaystyle \sum_{n=1}^{10}k_n \]
と表すことができる。これを一般化して、aからbまでの和を求めるとするなら、
\[ \displaystyle \sum_{n=a}^{b}k_n \]
だ。
ここで、\( k_1 = a \) だから
\[ \displaystyle
\begin{equation}
\sum_{n=a}^{b} k_n
\begin{cases}
= a & (n = a) \\
= k_1 + \displaystyle \sum_{n=a}^{b-1} k_n & (n > a)
\end{cases}
\end{equation}
\]
――という漸化式になる。高校で漸化式を習ったはずなので思い出しほしい。
ここで注目してほしいのは、for文のような繰り返し制御が数式に表れてこないことだ。結論を言うと、数学が表現する数式に繰り返し制御はない。その多くは漸化式で表すことができる。
Python は数学的なプログラミング言語なので、漸化式をプログラミングすることができる。
\[ 1+2+...+10 = k_{1} + k_{2} + ... k_{10} = \displaystyle \sum_{n=1}^{10}k_n \]
と表すことができる。これを一般化して、aからbまでの和を求めるとするなら、
\[ \displaystyle \sum_{n=a}^{b}k_n \]
だ。
ここで、\( k_1 = a \) だから
\[ \displaystyle
\begin{equation}
\sum_{n=a}^{b} k_n
\begin{cases}
= a & (n = a) \\
= k_1 + \displaystyle \sum_{n=a}^{b-1} k_n & (n > a)
\end{cases}
\end{equation}
\]
――という漸化式になる。高校で漸化式を習ったはずなので思い出しほしい。
ここで注目してほしいのは、for文のような繰り返し制御が数式に表れてこないことだ。結論を言うと、数学が表現する数式に繰り返し制御はない。その多くは漸化式で表すことができる。
Python は数学的なプログラミング言語なので、漸化式をプログラミングすることができる。
sumNaturalNumbers2.py
def sumNaturalNumbers2(a, b, n):
"""aからbまでの自然数の和を求めるユーザー関数（再帰呼び出し版）
Args:
a(int): 開始値
b(int): 終了値
Returns:
int 合計値
"""
if (n == a):
return n
else:
return n + sumNaturalNumbers2(a, b, n - 1)
プログラム "sumNaturalNumbers2.py" を実行してみてほしい。
ユーザー関数 sumNaturalNumbers2 は、aからbまでの自然数の和を求める漸化式を表す。if文を使って漸化式の場合分けをしているのだが、else の方ではユーザー関数 sumNaturalNumbers 自身を呼び出している。
プログラミング用語では、これを再帰呼び出し（リカーシブルコール）と呼ぶ。Python をはじめとするモダンな高級言語に備わっている機能だ。
ユーザー関数 sumNaturalNumbers2 は、aからbまでの自然数の和を求める漸化式を表す。if文を使って漸化式の場合分けをしているのだが、else の方ではユーザー関数 sumNaturalNumbers 自身を呼び出している。
プログラミング用語では、これを再帰呼び出し（リカーシブルコール）と呼ぶ。Python をはじめとするモダンな高級言語に備わっている機能だ。
階乗と三項演算子
再帰呼び出しの例としてよく取り上げられる階乗だが、数式で定義すると次のようになる。
\[n! =
\begin{cases}
\ 1 & \text{if } n = 1, \\
\ n \cdot (n-1)! & \text{if } n > 1.
\end{cases}
\]
これをPython で書くと、次のような関数になる。
\[n! =
\begin{cases}
\ 1 & \text{if } n = 1, \\
\ n \cdot (n-1)! & \text{if } n > 1.
\end{cases}
\]
これをPython で書くと、次のような関数になる。
factorial.py
def factorial2(n):
"""nの階乗を求める（再帰呼び出し）
Args:
n(bool): nの値
Returns:
int 階乗
"""
if (n == 1):
return n
else:
return n * factorial2(n - 1)
Python では、上記の定義のように場合分けが2つある数式に対し、if文を使わずに、1つの数式として記述できる三項演算子が備わっている。これを使ったのがユーザー定義関数 factorial3 だ。
factorial.py
def factorial3(n):
"""nの階乗を求める（再帰呼び出し＋三項演算子）
Args:
n(bool): nの値
Returns:
int 階乗
"""
return 1 if n == 1 else n * factorial2(n - 1)
returnに続く数式が1行しかないことが見て分かる。
ここで使われている if はif文ではなく、三項演算子である。
三項演算子を使った式は次のような構造をしている。
ここで使われている if はif文ではなく、三項演算子である。
三項演算子を使った式は次のような構造をしている。
A if α else B条件式αが成り立つときAを返し、そうでないときにはBを返す。
一方、繰り返し制御で階乗を表したのがユーザー定義関数 factorial1 だ。
プログラム "factorial.py" を実行してほしい。
プログラム "factorial.py" を実行してほしい。
factorial.py
def factorial1(n):
"""nの階乗を求める（繰り返し制御）
Args:
n(bool): nの値
Returns:
int 階乗
"""
y = 1
for i in range(2, n + 1):
y *= i
return y
繰り返し制御を使わずに漸化式をユーザー関数にする書き方を関数型プログラミングと呼ぶ。
複利計算
「4.3 for文」や「4.4 while文」といった繰り返し制御で取り上げた複利計算も、再帰呼び出しを使って実現できる。プログラム "calcCompoundInterest5.py" を実行してみてほしい。
calcCompoundInterest5.py
def calcCompoundInterest5(deposit, interest, period):
"""複利計算（再帰呼び出し版）
Args:
deposit(int): 現在の預金額
interest(float): 年間利率
period(int): 期間（年）
Returns:
int 複利計算後の預金額
"""
if period == 0:
return deposit
else:
return int(calcCompoundInterest5(deposit, interest, period - 1) * (1 + interest))
ニュートン法
newtonsSqrt2.py
def newtonsSqrt2(x, y, e):
"""ニュートン法を用いて平方根を求める（再帰呼び出し）
Args:
x(float): 計算中の平方根
y(float): 平方根を求めたい数
e(floa): 許容誤差
Returns:
float 平方根(近似値)
"""
# ニュートン法で新しいyを求める
x2 = x - (x * x - y) / (x * y)
# 誤差範囲より大きければ再帰呼び出し
if (math.fabs(x2 - x) >= e):
x2 = newtonsSqrt2(x2, y, e)
return x2;
フラクタル図形
図形のある部分を切り出すと、それが全体と相似になっている（自己相似）になっているものをフラクタル図形と呼ぶ。2011年（平成23年）に放映されたアニメ「フラクタル」のオープニング映像にマンデブロ集合使われていたことが記憶に残っているかもしれない。
自己相似は、再帰呼び出しによって実現できる。そして、自然界では、至るところでフラクタル図形を見ることができる。たとえばシダの葉――プログラム "BarnsleyFern.py" を実行してみてほしい。
自己相似は、再帰呼び出しによって実現できる。そして、自然界では、至るところでフラクタル図形を見ることができる。たとえばシダの葉――プログラム "BarnsleyFern.py" を実行してみてほしい。
BarnsleyFern.py
def dwawFern(x, y, depth):
"""バーンスレーのシダを描く
Args:
x(float), f(float): プロット座標
depth(int): 深さ
Returns:
None
Note:
plt: 外部ライブラリMatplotlib
"""
if depth <= 0:
return
r = random()
if r < 0.02:
x, y = 0.5, 0.27 * y
elif 0.02 <= r <= 0.17:
x, y = -0.139 * x + 0.263 * y + 0.57, 0.246 * x + 0.224 * y - 0.036
elif 0.17 < r <= 0.3:
x, y = 0.17 * x - 0.215 * y + 0.408, 0.222 * x + 0.176 * y + 0.0893
elif 0.3 < r <= 1.0:
x, y = 0.781 * x + 0.034 * y + 0.1075, -0.032 * x + 0.739 * y + 0.27
# 描画
plt.plot(x, y, "o", color = "green", markersize = 1)
dwawFern(x, y, depth - 1)
ユーザー定義関数 dwawFern は、グラフ描画に使った外部ライブラリ Matplotlib を使って点をプロットするだけのプログラムなのだが、再帰呼び出しをすることによって、あたかもシダの葉のように見える。このプログラムは、イギリスの数学者マイケル・バーンズリーにちなんで、バーンズリーのシダと呼ばれる。
フラクタル図形の代名詞となっているマンデブロ集合を描くプログラム "MandebrotSet.py" を実行してみてほしい。
MandebrotSet.py
def mandelbrot(c, z=0, n=0, maxIter=256):
"""複素数列を計算する
Args:
c(float), z(float), n(float): 複素数列
maxIter(int): iterの最大値
Returns:
None
"""
if abs(z) > 2 or n >= maxIter:
return n
return mandelbrot(c, z * z + c, n + 1, maxIter)
def generateMandelbrot(width, height, xMin, xMax, yMin, yMax, maxIter):
"""マンデブロ集合を生成する．
Args:
width(int): 画面の幅
height(int): 画面の高さ
xMin(int), xMax(int), yMin(int), yMax(int): X,Y座標の最小・最大値
maxIter(int): iterの最大値
Returns:
[x, y]: マンデブロ集合
"""
image = np.zeros((height, width))
for x in range(width):
for y in range(height):
re = xMin + (x / width) * (xMax - xMin)
im = yMin + (y / height) * (yMax - yMin)
c = complex(re, im)
color = mandelbrot(c, maxIter = maxIter)
image[y, x] = maxIter - color
return image
左図のように表示すれば成功である。
漸化式で示す複素数列を計算するユーザー関数 mandelbrot が再帰呼び出しになっている。
漸化式で示す複素数列を計算するユーザー関数 mandelbrot が再帰呼び出しになっている。
再帰呼び出しのメリットとデメリット
冒頭の漸化式の定義から明らかなように、再帰呼び出しは終了条件が単純明快である。したがって、無限ループに陥るリスクが減る――これがメリット。
一方で、バーンズリーのシダのプログラムの冒頭で、システムが扱える再帰呼び出しの深さを深く設定した。Python で、なぜ再帰呼び出しの深さに制約が掛かっているかというと、繰り返し処理に比べてリソースを消費するためだ。処理速度も低下するし、無制限に再帰呼び出しを行うとメモリが枯渇してしまう――これがデメリット。
一方で、バーンズリーのシダのプログラムの冒頭で、システムが扱える再帰呼び出しの深さを深く設定した。Python で、なぜ再帰呼び出しの深さに制約が掛かっているかというと、繰り返し処理に比べてリソースを消費するためだ。処理速度も低下するし、無制限に再帰呼び出しを行うとメモリが枯渇してしまう――これがデメリット。
BarnsleyFern.py
# システムが扱える再帰呼び出しを深くする
MAX_DEPTH = 15000
sys.setrecursionlimit(MAX_DEPTH)
再帰呼び出しを適用する処理は、例外処理が発生しないものが望ましい。例外処理はやってできないことはないのだが、繰り返し処理よりロジックが複雑になるので、再帰呼び出しにするメリットがない。
もう1つ、いずれ取り上げる非同期処理が再帰呼び出し内で利用しているデータに影響を与えてはいけない。タイミングによって再帰呼び出しの動きが変わってしまうためだ。
再帰呼び出しは、このようにシステム全体に関わるメリット／デメリットがあるので、使うかどうかは必ず設計段階で決めること。
もう1つ、いずれ取り上げる非同期処理が再帰呼び出し内で利用しているデータに影響を与えてはいけない。タイミングによって再帰呼び出しの動きが変わってしまうためだ。
再帰呼び出しは、このようにシステム全体に関わるメリット／デメリットがあるので、使うかどうかは必ず設計段階で決めること。
練習問題
次回予告
Python には、複数のデータをひとまとめのデータとして扱うコンテナデータ型として、リスト、配列、タプル、集合型、辞書型などが用意されている。これらを活用することで、Excelやデータベースのデータを取り出して計算処理したり、ゲームのパラメータやシナリオを管理することができる。
次回は、リストと配列の使い方を学ぶ。
次回は、リストと配列の使い方を学ぶ。
コラム：再帰呼び出しとメモリ消費
初期のアセンブリ言語やFORTRANは再帰呼び出しができなかった。私がはじめて再帰呼び出しを書いたのはC言語のプログラムだった。教科書に出てくるハノイの塔をプログラミングした。
その後、8ビットCPUのCコンパイラを日本語対応させたのだが、このとき、アセンブリで再帰呼び出しを可能にする仕組みを盛り込まなければならない。アセンブリは再帰呼び出しができないからだ。
その後、8ビットCPUのCコンパイラを日本語対応させたのだが、このとき、アセンブリで再帰呼び出しを可能にする仕組みを盛り込まなければならない。アセンブリは再帰呼び出しができないからだ。
再帰呼び出しの基本的な仕組みは、今も昔も変わらない。自分自身を呼び出す前に、ローカル変数やCPUの状態、レジスタやプログラムカウンタを、いったん保管する。そして関数から戻るときに、保管したデータを元に戻す。
再帰呼び出しが深くなればなるほど〈保管する場所〉が多く必要になるが、保管と取り出しは一対で起きる。そこで、スタックを用意した。
再帰呼び出しが深くなればなるほど〈保管する場所〉が多く必要になるが、保管と取り出しは一対で起きる。そこで、スタックを用意した。
8ビット用のCコンパイラはシングルスレッドで、クラスも作ることができないから、スタックに保管するデータ量はそれほど多くない。しかし、Pythonともなると、かなりのメモリを消費するだろう。本文に記したように、だから、Pythonでは再帰呼び出しの深さを制限している。
（この項おわり）
以前学んだ、1から10の和や、複利計算、ニュートン近似法を再帰呼び出しで書き直してみる。また、自然界によく見られるフラクタル図形を描くのにも再帰呼び出しが利用できる。