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) を呼び出している。 これが､関数の再帰的定義の実例でである。 

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def multi5(n):
    m = 5
    if n == 0:
        return 0
    else:
        return multi5(n - 1) + m

n = int(raw_input("inpu n = "))
print "5 x",n ," = ", multi5(n)
演習： 上のスクリプト multi5_recr.py を実行しなさい。

階乗

非負整数 $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} \]
演習： 非負整数 $n$ の階乗の値を返す関数 fact(n) を再帰的に定義し、キーボード入力から非負整数文字列を入力し、その値を出力するスクリプト fact.py を書きななさい。 さらに、階乗を再帰呼び出しを使わずfor文で計算する関数 fact_for(n) もあわせて定義し、同じ結果になるのであるが、それぞれ fact(n) と fact_for(n) 関数で計算した結果を出力するようにし、実行してみなさい。 なにか別の発見もあるはずだ。

ベキ乗

実数 $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} \]
演習： 上の2つの方法で　ベキ乗を計算する再帰的関数 power_a(x, n) および power_b(x, n) を定義し、y = 3.1415 とスクリプト内で与えておいて（あるいはキー入力を float() でキャスとして浮動小数として変数に代入してもよい）、キーボード入力からベキ指数である正整数文字列を入力して整数 n とし、$y^n$ の値をそれぞれの関数を使って出力するスクリプト power.py を書きななさい。 同じ値になっているだろうか。

リスト要素の和と計算時間の測定

数を要素とするリスト 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' はタブ文字である）。 今後計算時間の取得は大切になる。 

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random
import time

def sum_list(num_list):
    sum = 0
    for i in num_list:
        sum += i
    return sum

n = int(raw_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
演習： スクリプト sum_list.py を実行してみなさい。

数リスト 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:])
演習： 先のスクリプト sum_list.py に関数 sum_list_recur(num_list) の定義を加えて、次のような結果となるように書き換えなさい。 計算時間の差を含めて何か別の発見もあるはずだ。 
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条件を満たしている必要がある。

  1. 再帰アルゴリズムは基礎計算レベルを持つこと（自明計算の存在）
  2. 再帰アルゴリズムはその状態を変化させて、基礎計算レベルに向かうこと（再帰計算の終了性）
  3. 再帰アルゴリズムは自分自身を呼び出していること（自己言及）

自明計算の存在は、簡単で容易に解決できる「小さな問題」に分解されていることである。 再帰計算の終了性は、「大きな問題」が自明計算に向かうようにアルゴリズム設計されているかである。 自己言及は、アルゴリズムの定義において、自分自身のアルゴリズムを使って表現することである。

自明計算の存在と再帰計算の終了性が示唆するように、再帰的アルゴリズムは分割統治法（divide and conquer）の一例である。

演習： 次のAckermann関数 \begin{align*} & A(0,y) = y+1\\ & A(x+1,0) =A(x,1)\\ & A(x+1,y+1) =A(x,A(x+1,y)) \end{align*} をPythonで定義し、整数値 $x$ と$y$ をそれぞれキーボード文字列から読み込んで、その値 $A(x,y)$を計算するスクリプト ackermann.py を書きなさい。 $x$ または $y$ を1つ増やすときの計算時間は変化はどうかも併せて観測しなさい。

（ヒント）$A(x, y)$は次のようにも考えることができる。 \begin{align*} & A(0,y) = y+1\\ & A(x,0) =A(x-1,1)\\ & A(x,y) =A(x-1,A(x,y-1)) \end{align*}

再帰関数の前方参照

次のようなPythonスクリプトはちゃんと値が返る。 関数 func_a の定義でそれよりも前方にある関数 func_b を呼び出し、その関数 func_b の定義でも関数 func_a を呼び出して再帰的に相互参照している。 その動作を理解できるだろうか。 

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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)
演習： 上のスクリプト mutual_refer.py を実行しなさい。 その結果はどのように計算されたのかを説明しなさい。

しかし、16行目にある print func_a(5) を 4行目の def func_a(a): 行よりも上に移動すると、次のようなエラーが返る。 

./mutual_refer.py
Traceback (most recent call last):
  File "./mutual.py", line 4, in 
    print a(6)
NameError: name 'a' is not defined
演習： 実際にエラーが発生することを確かめなさい。

Pythonの前方参照の禁止は、実行時に定義されていない手続きや関数の呼び出しを禁止するものであり、たとえば、関数の相互参照は可能である。