6. 関数、再帰関数、そして高階関数¶

より抽象度の高いプログラミングを目指して、関数、ラムダ式、高階関数の考え方を習得します。

36f803dfce3548628def7d36729be6cc

6.1. 関数を定義する¶

今まで、print(x)関数やmax(x,y)を使ってプログラミングをしてきました。今回は、まず関数を定義する方法を覚えましょう。

6.1.1. 関数定義¶

関数定義は、def文を用いて行います。

関数定義の構文

def 関数名(パラメータ):
  関数本体のコード(値を計算する)
  return 値

例題（関数定義）

次の関数を定義してみよう。

\(f(x) = x + 1\)
\(f(x) = x + a\)
\(f(a, b) = \begin{cases} a & (a>b) \\ b & (otherwise) \end{cases}\)
\(f(x) = \begin{cases} 1 & (n=0) \\ x \cdot x^{n-1} & (otherwise) \end{cases}\)

1.: \(f(x) = x + 1\)

パラメータはx, 関数の結果はx+1になります。関数の結果は、return文を用いて返すようにします。

[1]:

def f(x):
    return x + 1

一旦、関数を定義してしまうと、あとは、f(0), f(1)のように用いることができます。

[2]:

for i in range(10):
    print(f'f({i}) =', f(i))

f(0) = 1
f(1) = 2
f(2) = 3
f(3) = 4
f(4) = 5
f(5) = 6
f(6) = 7
f(7) = 8
f(8) = 9
f(9) = 10

関数本体に書けること

Python の関数は、パラメータを受け取り、計算して結果を返すプログラムです。途中で、任意のPython コードを用いて計算することができます。

def f(x):
    print('引数': x)
    a = x + 1
    return a

returnが最終的な関数の評価結果になります。 return以降のコードは（もし書いてあったとしても）無視されます。

2: \(f(x) = x + a\)

ちょっと数学にありがちな「その\(a\)はどこから出てきたのかな？」と思ってしまう関数定義です。次の２通りの実装方法があります。

[3]:

## xもaもパラメータ化する
def f(x, a):
    return x + a

[4]:

## a をグローバル変数にする
a = 1
def f(x):
    return x + a

グローバル変数とローカル変数

グローバル変数は、トップレベルで定義された変数で全ての関数から参照することができる。一方、ローカル変数は関数内で定義された変数で関数内でのみ参照することができる。

3. \(f(a, b) = \begin{cases} a & (a>b) \\ b & (otherwise) \end{cases}\)

いわゆるmax(a,b)を定義します。

[5]:

def f(a, b):
    if a > b:
        return a
    else:
        return b

[6]:

def f(a, b):
    if a > b:
        return a  # 一度、return したら、それ以降は無視される
    return b

[7]:

def f(a, b):
    return a if a > b else b  # 条件式

4. \(f(x,n) = \begin{cases} 1 & (n=0) \\ x \cdot x^{n-1} & (otherwise) \end{cases}\)

n乗を計算しています。

ここで、\(f(x, n) = x^{n}\)ということに注意すれば、\(f(x, n) = \begin{cases} 1 & (n=0) \\ x \cdot f(x,n-1) & (otherwise) \end{cases}\)

これを素直に直すと：

[8]:

def f(x, n):
    if n == 0:
        return 1
    return x * f(x, n-1)

[ ]:

f(5, 5)  # 5の3乗

再帰関数(recursive function)

自分自身を再度呼び出す関数のこと

6.1.2. 値を返さない関数¶

Python の関数は、値を返す必要はありません。プログラムの機能単位にまとめて、関数を定義することができます。

例題（長方形の描画）

次の関数を定義してみよう。

rect(w, h): 縦h横wの長方形を#で表示する
square(w): 縦w横wの正方形を#表示する

出力: rect(4, 3)

####
####
####

素直に、二重ループを用いて長方形を書いてみます。

[9]:

def rect(w, h):
    for y in range(h):
        for x in range(w):
            print('#', end='') #改行なしで #を出力
        print() # 改行

rect(4, 3)

####
####
####

正方形は、長方形の縦横の長さが等しい場合なので..

[10]:

def square(w):
    rect(w, w)
square(5)

#####
#####
#####
#####
#####

関数を作るタイミング

どこをどう関数化するかを判断するのは難しいところです。最初は、練習をかねて積極的に関数化していきましょう。

6.2. 再帰とは¶

再帰 (recursion) とは、あるものについて記述するときに、それ自身への参照が含まれる形式の記述のことです。

例アメリカ合衆国憲法の条文(抜粋) によるアメリカ市民とは、

アメリカ合衆国内で生まれた子供
もしくは、アメリカ市民の子供

数学では、漸化式の形式でよくあらわれます。

例: 階乗 \(a_n = n!\)

\(a_n = \begin{cases} 1 & (n=1) \\ n \cdot a_{n-1} & (n>1) \end{cases}\)

6.2.1. 繰り返しと再帰関数¶

繰り返しは、「再帰関数で書き直せますよ」という話を例題で示します。

例題（階乗）

\(n!\)を求める関数factorial(n)を定義してみよう。

まず、繰り返しで解いてみます。

\[n! = n \times n-1 \times ... \times 2 \times 1\]

なので、\(\times\)の数に注目すると、\(n-1\)回、掛け算することになります。繰り返す回数がわかれば、あとは\(N\)回繰り返す構文を用いて計算します。

[11]:

def factorial(n):
    result = 1
    for i in range(2, n+1):
        result = i * result
    return result
print(factorial(5))

再帰関数による解法

\(factorinal(n)=n!\)なので、

\(factorial(n) = \begin{cases} 1 & (n=1) \\ n \cdot factorial(n-1) & (n>1) \end{cases}\)

[12]:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))

再帰構造とループ

再帰構造はループ (while 文, for 文) とプログラム意味論的には等価です。

ループは再帰で書き直すことができる.
再帰はループで書き直すことができる.

どちらが良いか?

プログラマは、次のように派閥がわかれています。

ループ派: まずはループで書く
再帰派: とにかく何でも再帰で書く

ループの利点

性能がよい
スタックオーバーフロー (stack overflow) を心配しなくてよい.

再帰の利点

コードから、数学的な意味が把握しやすい
末尾再帰の最適化がない言語は使わなければよい（意味不明）

注意

倉光は再帰派（少数）なので、再帰に対し好意的です。

6.2.2. スタックオーバーフローとは何か？¶

再帰関数を書くときは、スタックオーバーフローに注意しましょう。

スタック・オーバーフロー (stack overflow) は、再帰関数に限らずに関数のコールスタックを使い切ったときに発生します。プログラミングでは、わりとよく発生するバグです。

コールスタック

プログラミング言語は、関数の引数やローカル変数はスタックデータ構造に保存しています。

関数を適用(コールする)と、引数とローカル変数は push される
関数をリターンすると、pop される

コールスタックは有限なのでスタック・オーバーフローが発生します。

コールスタックと再帰関数の関係は、最初の factorial(n)にprint()を入れて、確認しておきましょう。

[14]:

def factorial(n):
    print(f'引数{n}でコール')
    if n == 1:
        res = 1
    else:
        res = n * factorial(n-1)
    print(f'n={n}の結果として{res}を返す')
    return res

print(factorial(5))

引数5でコール
引数4でコール
引数3でコール
引数2でコール
引数1でコール
n=1の結果として1を返す
n=2の結果として2を返す
n=3の結果として6を返す
n=4の結果として24を返す
n=5の結果として120を返す
120

Let’s Try

スタックオーバーフローを発生させてみましょう

再帰関数では簡単に発生します。例えば、factorial(-1)などを呼んでみると、いつまでも再帰呼び出しを続けて、コールスタックを使い切ります。

実行するときは、print()はコメントアウトしておいた方がよいかも。

[15]:

def factorial(n):
    #print(f'引数{n}でコール')
    if n == 1:
        res = 1
    else:
        res = n * factorial(n-1)
    #print(f'n={n}の結果として{res}を返す')
    return res

print(factorial(-1))

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-15-2a6fc6f38288> in <module>
      8     return res
      9
---> 10 print(factorial(-1))

<ipython-input-15-2a6fc6f38288> in factorial(n)
      4         res = 1
      5     else:
----> 6         res = n * factorial(n-1)
      7     #print(f'n={n}の結果として{res}を返す')
      8     return res

... last 1 frames repeated, from the frame below ...

<ipython-input-15-2a6fc6f38288> in factorial(n)
      4         res = 1
      5     else:
----> 6         res = n * factorial(n-1)
      7     #print(f'n={n}の結果として{res}を返す')
      8     return res

RecursionError: maximum recursion depth exceeded in comparison

RecursionError: スタックオーバーフローのこと

RecursionError: maximum recursion depth exceeded in comparison

6.2.3. 閑話休題：入社面談より¶

google関数は、研究室の学生が過去 G 社の入社面談を受けたとき、ホワイトボードの前で「ちょっと書いてみて」と聞かれた設問です。

ホワイトボード・コーディング

面接でプログラミング力を試させること。ただ、書くだけでなく、エレガントなコーディングやセンスも問われる。

課題（入社面談より）

整数 x を反転させる関数 g(x) を定義してみてください。

g(x) の例

print(g(12))   # => 21
print(g(1234)) # => 4321
print(g(90))   # => 9

次回、回答例を示しますので、腕試しで g(x) を定義してみよう。もちろん、エレガントかどうかは置いておいて、コーディングセンスも問われます。

6.3. ラムダ式と高階関数★¶

ラムダ式や高階関数は、もともと関数型プログラミング言語に由来し、Python では上級？技法（少なくとも初心者むけの技法ではない）に位置するものです。

だから、飛ばしてもらっても構いませんと言いたいところですが、３年生むけのデータサイエンスや機械学習では、容赦なく使われるのでやはりここでしっかり抑えておいて欲しいです。

この章

知っておいて欲しいけど

6.3.1. 関数も値¶

Python3 は、関数自体も整数や文字列などと同じく、値として扱えるようになっています。このような関数のことを、第一級オブジェクト (first-class object) とも呼びます。

まず、関数が値であるとはどういうことなのか確認しておきましょう。数値をひとつ増やす succ(n) 関数を定義してみた例をみてください。

関数 succ(n) の定義

[16]:

def succ(x):
    return x+1

print(succ(0))

関数は、succ(0) のように引数を適用することで呼び出すことができます。実は、ここで succ という識別子は関数を値として保持している変数名にもなっています。だから、 type(succ) とすると、その値の型を調べることができます。

[17]:

type(succ)

[17]:

function

関数は、変数名 succ に代入された値なので、整数や文字列と同じように他の変数に代入することができます。すると、代入された変数名の方から、succ 関数を呼び出せるようになります。

[18]:

f = succ
print(f(0))

注意: 変数 f は、succ と同じ関数を参照しているため、f(0) は succ(0) と同じ結果となります。

6.3.2. ラムダ式¶

ラムダ式 (lambda expression) は、関数を値として、直接定義する記法です。関数名を付ける必要はないため、無名関数とも呼ばれます。先ほどの succ 関数は、ラムダ式を用いると、次のように直接、値として書き直すことができます。

[19]:

g = lambda x: x+1
print(g(1))

ラムダ式は、Aronzo Church の λ 計算 (λx.x + 1) に由来していますが、プログラミング言語のラムダ式は、単に、関数を値として定義するための記法に過ぎません。β 簡約や Church 数などを理解しなくとも、恐れるところはありません。

Python3 のラムダ式は、式しか与えることができません。つまり、制御構造などが含まれたプログラムは、ラムダ式として定義することはできず、def succ(n): の例のように、名前付きの関数として一旦、定義し、関数名から参照することになります。

6.3.3. 高階関数¶

高階関数 (high-order function) とは、「関数をパラメータにとる関数」のことです。関数が値として変数に代入できるなら、当然、関数もパラメータにできるわけですが、結果として、より抽象度の高い関数が定義できるようになります。

ここでは、代表的な高階関数である map 関数と filter 関数を例に高階関数の仕組みを理解していきましょう。

map関数

map(f,xs) のパラメータは、関数 f とリスト xs をとります。リストxsから、順番に要素を取り出し、各要素に関数 f を適用します。最終的に、新しいリストに関数 f の適用した結果を入れて、返します。

[20]:

def map(f, xs) :
    mapped = []
    for x in xs:
        mapped.append(f(x))
    return mapped

パラメータで渡せる関数は、定義済みの関数名、もしくはラムダ式になります。

[21]:

map(succ, [1, 2, 3])

[21]:

[2, 3, 4]

[22]:

map(lambda x : x * 2, [1, 2, 3])

[22]:

[2, 4, 6]

filter関数

filter(f,xs) のパラメータは、関数 f とリスト xs をとります。リストxsから、順番に要素を取り出し、各要素に関数 f でフィルタします。最終的に、関数fの適用結果が真だった要素だけのリストを作り、結果として返します。

[23]:

def filter(f, xs) :
    filtered = []
    for x in xs:
        if f(x):
            filtered.append(x)
    return filtered

[24]:

filter(lambda x: x % 2 == 1, [1, 2, 3])

[24]:

[1, 3]

なお、Python3 では、map 関数と filter 関数は組み込み関数として定義されているため、ふだんは自分で定義する必要はありません。

Let’s try

そろそろ、おなじみのmap(int, input().split())がどんな処理をしているか説明できますね。

6.3.4. 内包記法と高階関数¶

最後に、リスト内包記法はmap()関数とfilter()関数が融合した構文だと言うことを確認しておきましょう。

外延定義: \(A = \{ 1, 2, 3, 5, 8, 13, 21, 34, 55 \}\)

A = [1, 2, 3, 5, 8, 13, 21, 34, 55]

内包定義: \(B = \{ 2x | x \in A \}\)

B = [2*x for x in A]
B = list(lambda x: 2 * x, A)  # mapの描き直し

内包定義: \(C = \{ x | x \in A, \mbox{xは奇数} \}\)

C = [x for x in A　if x % 2 == 1]
C = list(filter(lambda x: x % 2 == 1, A))  # filter版

内包定義: \(D = \{ 2x | x \in A, \mbox{xは奇数} \}\)

D = [2 * x for x in A　if x % 2 == 1]
D = list(map(lambda x: 2*x, filter(lambda x: x % 2 == 1, A)))  # map,fliter版

内包記法

高階関数のmap()とfilter()をミックスしたことが簡単に書けます。 Pythonでは、内包記法を積極的に活用していきましょう。

6.4. 演習問題¶

できる限り、関数を定義して使っていきましょう。

ReLU
a+a2+a3: 関数定義しましょう！
エレベーター: 1F, 2F, 3Fを渡すと、数値に変換する関数を考えます。
大きい数字
とある総和
回文数
K進数: K進数に変換する関数を定義
スマホ中毒: 入力がめんどくさいので、ヒントを読もう
ほぼGCD: 正直、問題文の理解が一番むずかしい
FizzBuzzの和: 有名なFizzBuzz問題のバリエーション
入国審査
ビンゴ: ビンゴを判定する関数定義しましょう
ラリー
グリッド圧縮
文字列圧縮: ランレングス圧縮を関数化します。
７５５再帰関数を使います

6.4.1. ヒント：Colab上で入力がめんどくさく感じたら¶

Colab上で入力がめんどくさく感じたら、少し禁断のテクニックですが、 input()関数を書き換えてしまいましょう。

次のIn関数は、与えられた文字列を1行ずつinput()に渡すようにする関数です。

[25]:

def In(s): #Colab上で最初に一度定義する。
  global input
  import builtins
  data  = [line for line in s.split('\n') if len(line) > 0]
  def input_new():
    if len(data) > 0:
      return data.pop(0)
    else:
      input = builtins.input # 元に戻す
      return builtins.input()
  input = input_new

複数行にわたる入力文字列もトリプルクート(''')で囲んで渡すと、input()を置き換えます。

[26]:

In('''
10 2 20
9 11
13 17
''')

すると、渡した入力文字列がある間は、順番に渡されるようになります。

[27]:

input()

[27]:

'10 2 20'

[28]:

input()

[28]:

'9 11'

[29]:

input()

[29]:

'13 17'

必ずいるので注意

AtCoder に提出するときは、In(...)の部分は入れないでください。 input()を書き換えるので、正しくAtCoderの入力が読めなくなります。

Python Programming 2021 ドキュメント