再帰関数 Recursive Function
***はじめに***
私自身プログラミング自体初めてなので内容に誤りがあるかもしれません。あくまでも自分で分かりやすいようにまとめる自分用のノートなのでご理解のほど宜しくお願いします。間違ってたらそっと優しく教えてください。あとちょいちょい英語なのは日本語での上手い訳し方が分からないからです。ちなみに言語はpython３系です。
再帰関数とは、自分自身を呼び出して似たような操作を繰り返すような関数。
この「似たような操作」という点が大事。基本的に同じアルゴリズムを繰り返すものは再帰関数で書くとコードが読みやすくなるという利点がある（反面、メモリを食うことが多いので基本的に使う事はあまりないとプログラマーの友達が言ってた）。
再帰関数を書くにあたって、３つの要素を考える必要がある。ここでは例として階乗の計算を考えてみる。
⒈ Figure out the base case.
終了条件を考える。基本的な（簡単な）再帰関数は大抵if文の中に終了条件とその結果をリターンしている事が多い。
階乗の場合、０や１の階乗は定義より１なので、 return 1 としておく。また、次で述べるが引数は基本的に減っていく事が多いので、この時のif文を n == 0 （引数がどんどん引かれて、最終的に０になった場合。階乗は０から始まる自然数が定義域（domain）なので、 n == 0 が終了条件として望ましい）とする。
⒉ Make a recursive call with a simpler argument.
元々の問題よりも範囲を小さくして考えてみる。大抵は引数の値を減らしたものを使う事が多い。
階乗の計算であれば、例えば３！を求めたいとする。３！は３＊（３−１）！、つまり３＊２！で表せる。この（３−１）！に相当する部分がこのrecursive callになる。これを一般的に書くと、n！＝n＊（nー１）！と表せる。
⒊ Use your recursive call to solve the full problem.
２で求めた再帰表現を使って、元々の問題をどう解くかを考える。先ほど３の階乗の例で既に書いたが、３＊（３−１）！で３！を求められるので、この表現を使ってコードを書く。そして忘れてはならないのが、再帰関数は「自身を返す関数」なので、returnに自分自身が入る。
これらを踏まえて階乗の計算をするプログラムを書くと、
- def factorial(n):
- if n == 0: # Base case. 終了条件
- return 1
- else:
- return n * factorial(n-1) # 自身（factorial）を返し、かつn！の答えである。
練習問題１
再帰関数を使って二つの数字のかけ算を計算するプログラムを作りなさい。二つの数字は正とし、また掛け算記号である*やmulは使ってはいけない。
def multiply(m, n):
"""
>>> multiply(5, 3)
15
"""
# 以下答え
if n == 0: # Base case
return 0
else:
return m + multiply(m, n-1). # 5 + multiply(5, 2) = 5 + 5 + multiply(5, 1) = 5 + 5 + 5 + multiply(5, 0) = 5 + 5 + 5 + 0 = 15
練習問題２
nから１までをカウントダウンしてプリントする関数を再帰関数を使って書きなさい。
def countdown(n):
"""
>>> countdown(3)
3
2
1
"""
# 以下答え
if n == 0:
return # カウントダウンが０になった時は何もしない
print(n)
countdown(n-1) # countdown(n-1)→print(n-1)→countdown(n-2)...の繰り返し
練習問題３
練習問題２のコードを書き換えて、カウントアップを表示するプログラムを書け。
def countup(n):
"""
>>> countup(3)
1
2
3
"""
if n == 0:
return
countup(n-1)
print(n) # countdown(n-1)とprint(n)の位置を入れ替えただけ
練習問題４
再帰関数を使って一番右の桁から飛び飛びの数字の合計を求めるプログラムを書け。
def sum_every_other_digit(n):
"""
>>> sum_every_other_digit(7)
7
>>> sum_every_other_digit(30)
0
>>> sum_every_other_digit(1234567) # 7 + 5 + 3 + 1
16
"""
# 以下答え
if n == 0:
return 0
else:
return n % 10 + sum_every_other_digit(n // 100) # n % 10で一番右の桁、n // 100でその次の次の桁までの数字を表す
関数の中に別の関数を定義して再帰関数を作ることも出来る。
このように中で定義される関数をhelper functionと呼んだりする。
練習問題５
helper function prime_helperを定義して素数かどうかを判定する再帰関数を書け。
def is_prime(n):
"""
>>> is_prime(7)
True
>>> is_prime(10)
False
>>> is_prime(1)
False
"""
def prime_helper(k):
# 以下答え
if k == 1: # Base case. 自身以外に割り切れる数字がない場合True
return True
elif k == 0 or n % k == 0: # n=1または他に割り切れる数字がある場合
return False
else:
return prime_helper(k-1) # 再帰表現
return prime_helper(n-1) # チェックはprime_helperに任せる
練習問題６
合成関数を指定回数繰り返すプログラムを書け。
英版：Define a function make_func_repeater which takes in a one-argument function f and integer x. It should return another function which takes in one argument, another integer. This function returns the result of applying f to x this number of times. Make sure to use recursion in your solution.
def make_func_repeater(f, x):
"""
>>> incr_1 = make_func_repeater(lambda x: x + 1, 1) # f(x) = x + 1, x = 1
>>> incr_1(2) # f(f(1)) = f(1 + 1) = (2) + 1 = 3
3
>>> incr_1(5) # f(f(f(f(f(1))))) = f(f(f(f(1+1)))) = f(f(f(2+1))) = f(f(3+1)) = f(4+1) = 5 + 1
6
"""
def repeat(i):
# 以下答え
if i == 0: # これ以上繰り返さない場合
return x
else:
return f(repeat(i - 1))
return repeat
再帰関数を書く時は、returnから消去法で埋めていくといいかも。
次に終了条件を考えて、最後に再帰方法を考える。
次回はTree Recursionについて。基本的には同じなんだけど、一度に複数の再帰を扱う場合のもの。
てかいちいちコードのインデント打つのだるいから今度から画像貼り付けにしようか…
