Webページでは数式を表すためにLaTeX表記が使えるMathJaxを利用しています。
WebブラウザにはSafari/Chrome/Firefoxを使って下さい(IEでは表示できないようです。)
関数の再帰的定義
掛け算
整数の掛け算 $m \times n$ の意味は誰でも知っている($n=0,1,2,\dots$としておこう)。$m$が与えられた数としたとき、$m\times n$は$m$を$n$倍する、つまり$n$回足し合わせた数である。 \[ m \times n = \underbrace{m + m + \dots + m}_{\text{$n$回}} \]
したがって、掛け算は足し算さえできればできるので、九九を覚えるのは計算が早くするためだ。 しかし、この当たり前に理解しているこの事実は非常に重要な概念を含んでいる。 それが関数の再帰的定義である。 再帰呼び出し(recursive call)は多くのプログラミング初心者をまごつかせている。 その理由は掛け算が理解できていないのかもしれない。 掛け算がわかっているのであれば、以下のように再帰呼び出しは至って自然なことであることが了解される。
与えられた数 $m = 5$ を $n$ 倍するという掛け算 $5\times n$ を $\mathrm{multi5}(n)$ と書くことにしよう。 次のことが当たり前のことだと理解すれば、それが関数の再帰的定義である。
\begin{align*} \mathrm{multi5}(n) &= \underbrace{\big(m + \dots + m\big)}_{\text{$n-1$回}} + m\\ &= \mathrm{multi5}(n - 1) + m \end{align*}実際に、この考えが動作することをPythonで確かめることができる。 次の multi5_recr.py は、11行目でキー入力された数字文字列を整数にキャストして、変数 n に代入している。 関数 multi5(n) は、内部で m に値 5 をセットして、仮引数のとで $5 \times n$の値を返すように定義している。 もし $n$ が 0 であれば、値 0 を返し、そうでなければ($n>0$を前提にしている)値として multi5(n - 1) + 5 を返す。 関数 multi5(n) を定義するために、自分自身の関数、ただし、引数が n - 1 とした multi5(n - 1) を呼び出している。 これが、関数の再帰的定義の実例でである。
def multi5(n): m = 5 if n == 0: return(0) else: return(multi5(n - 1) + m) n = int(input("inpu n = ")) print('5 x', n ,' = ', multi5(n))
階乗
非負整数 $n$ の階乗(factorial)は、 初等的な教科書には $n!=n\times (n-1)\times 2\times 1$であると書いてある。 ここでは次のように定義しよう。 ゼロの階乗 0! = 1としていることが少し「高級」である(1! 以外に 0! を 1 としておくと何かと都合が良いからだ)。
\[ n! =\begin{cases} 1 & \text{if $n=0$},\\ n \times (n-1)! & \text{if $n>0$} \end{cases} \]ベキ乗
実数 $x $ の正整数 $n$ のベキ乗 $x^n$ を計算する関数 power(x, n) を考えよう。 再帰的定義としては次の2つの方法が考えられる。
\[ a)\quad x^n = \begin{cases} 1 & \text{if $n=0$},\\ x \times x^{n-1} & \text{if $n>0$}. \end{cases} \qquad b) \quad x^n = \begin{cases} 1 & \text{if $n=0$},\\ x^m \times x^m & \text{if $n=2m$},\\ x^m \times x^m \times x & \text{if $n=2m+1$}. \end{cases} \]リスト要素の和と計算時間の測定
数を要素とするリスト num_list の要素の合計を計算する関数 sum_list(num_list) を定義する(num_list は空でないと仮定する)。
次の sum_list.py では、乱数モジュール random をインポートし(4行目)、キーボードから入力された整数文字列を整数にキャストして変数 n に代入する(13行目)。 0 から n + 99 まで(n + 100) 個の整数リスト range(n + 100) から、ランダムに n 個の要素を取り出したランダム整数リスト nlsit を作成(14行目)して、その要素の合計を関数 sum_list(nlist) を呼び出して出力する(20行目)。
関数 sum_list(num_list) は、渡された数リストを for文のカウント変数 i にセットして次々に加えることで、数リスト要素の合計を返すように定義する。
ここでは、5行目に time モジュールをインポートしている。 16行目と18行目でそれぞれ time.time() で浮動小数点数で返される時刻(単位は UTC におけるエポックからの秒数)を取得して、それぞれ start と end に代入し、結果、19行目で sum_list(nlist) の計算に要した時間を表示している('\t' はタブ文字である)。 今後計算時間の取得は大切になる。
import random import time def sum_list(num_list): sum = 0 for i in num_list: sum += i return(sum) n = int(input('generating random lists with length n (> 0) = ')) nlist = random.sample(range(n + 100), n) start = time.time() for_sum = sum_list(nlist) end = time.time() print('For version: used time: ', end - start, '[sec]') print('\tfor version: sum of list = ', for_sum)
数リスト num_list の要素を合計する関数 sum_list(num_list) を再帰呼びで定義する関数 sum_list_recur(num_list) は次のようになる。
空でないリスト num_list の長さが 1 つまり要素が1つであるときリストの先頭要素 num_list[0] を返す。 そうでない(長さが2以上ある)ときには、リストの先頭要素 num_list[0] に、 num_list の1番目以降最後までのリスト num_list[1:] を引数とした長さが1つだけ短い数リストを sum_list(num_list[1:]) で計算した値を加える、と定義している。 sum_list_recurの関数定義内部で、自分自身 sum_list_recur を呼び出している。
def sum_list_recur(num_list): if len(num_list) == 1: return(num_list[0]) else: return(num_list[0] + sum_list_recur(num_list[1:]))
Number of elements in random list = 200 For version: used time: 5.29289245605e-05 for version: sum of list = 29748 Recursive version: used time: 0.000211000442505 sum of list = 29748
再帰呼び出しの3つの原則
あらゆる計算は再帰的関数、つまり
いままでの例がそうであったように、関数やアルゴリズムを再帰的に定義するためには次の3条件を満たしている必要がある。
- 再帰アルゴリズムは基礎計算レベルを持つこと(自明計算の存在)
- 再帰アルゴリズムはその状態を変化させて、基礎計算レベルに向かうこと(再帰計算の終了性)
- 再帰アルゴリズムは自分自身を呼び出していること(自己言及)
自明計算の存在は、簡単で容易に解決できる「小さな問題」に分解されていることである。 再帰計算の終了性は、「大きな問題」が自明計算に向かうようにアルゴリズム設計されているかである。 自己言及は、アルゴリズムの定義において、自分自身のアルゴリズムを使って表現することである。
自明計算の存在と再帰計算の終了性が示唆するように、再帰的アルゴリズムは分割統治法(divide and conquer)の一例である。
再帰関数の前方参照
次のようなPythonスクリプトはちゃんと値が返る。 関数 func_a の定義でそれよりも前方にある関数 func_b を呼び出し、その関数 func_b の定義でも関数 func_a を呼び出して再帰的に相互参照している。 その動作を理解できるだろうか。
def func_a(a): if a == 1: return(1) else: return(a * func_b(a - 1)) def func_b(b): if b == 1: return(1) else: return(b + func_a(b - 1)) print func_a(5)
しかし、16行目にある print func_a(5) を 4行目の def func_a(a): 行よりも上に移動すると、次のようなエラーが返る。
./mutual_refer.py Traceback (most recent call last): File "./mutual.py", line 4, inprint a(6) NameError: name 'a' is not defined
Pythonの前方参照の禁止は、実行時に定義されていない手続きや関数の呼び出しを禁止するものであり、たとえば、関数の相互参照は可能である。