Python で再帰関数

「Python で お絵描きたぁぃむ」でグラフィックを扱ったのに続いてフラクタル（自己相似性）画像をやりたかったのですが、難しそうなのと Bitarrow で対応していないのを理由に取り止めます。その代わりと言っては何ですが、再帰関数を取り上げます。というのは、フラクタルと再帰関数は構造が似ているし、Python でフラクタルを作ろうとすると再帰関数がほぼ必須だからです。そして難易度もちょうど良い。
　フラクタルは「自分自身の中に自分と同じ形のものが入っている」ことであり、再帰関数は「関数が自分自身を関数として呼び出す」ことです。

　再帰関数の基本形は次のようなものです。再帰関数はその形から無限ループに陥りそうで、そうならないように「終了条件」を明確に書くことが大事です。

def 関数名(n):
    if （終了条件）:
        return x
    （処理）
    return 関数名(n-1)  # ← 元と同じ名前の関数を返す

関数名(n)    # ← メインのコードの中で関数を実行する

　では、３つばかり練習しましょう。

階乗

【実習１】 自然数 n を入力して、n の階乗の値を表示する。

　「10!＝10×9×8×7×6×5×4×3×2×1」ですが、次のように捉えましょう。

10!＝10×9!
　　　　└→ 9!＝9×8!
　　　　　　　　　└→ 8!＝8×7!
　　　　　　　　　　　　　　　：
　　　　　　　　　　　　　　　　　└→ 2!＝2×1!
　　　　　　　　　　　　　　　　　　　　　　└→ 1!＝1

　一番下が「終了条件」です。いつまでも階乗！が続いたのでは永遠に値が出ませんから、終わるタイミングを教えてあげましょう。
　高校生なら、このことを数列の漸化式で捉えると良いかもしれません。

$${a_1=1}$$
$${a_n=n\cdot a_{n-1}}$$

　数列で言うと初めの式が初期条件ですが、再帰関数で言うとこれが終了条件に当たります。言葉は違えど、働きは一緒です。そして２つ目の漸化式は、言い換えれば再帰そのものですね。

def factrical(n):
    if n==1:                    # 「if n==0:」 とすると 0!=1 にも対応する
        return 1
    return n*factrical(n-1)

n=int(input("階乗")
print(n,"!=",factrical(n))

和（Σ計算）

【実習２】 自然数 n を入力して、1 から n までの和を表示する。

　数列の和Σの公式を知っているなら

print((n+1)*n/2)

で良いんですが、ここでは練習のつもりで再帰関数を使ってみてください。
　これを漸化式で書くと、

$${s_1=1}$$
$${s_n=s_{n-1}+n}$$

となりますから、

def sum(n):
    if n==1:
        return 1
    return sum(n-1)＋n

n=int(input("和")
print("１から",n,"までの和は、",sum(n))

でいけそうです。

ユークリッドの互除法

【実習３】 自然数 a , b を入力して、a と b の最大公約数を表示する。

　ユークリッドの互除法 とは、定理「a を b で割ったときの余りを r とすると〈a と b の最大公約数〉と〈b と r の最大公約数〉は一致する」を使って、下のような手順で〈a と b の最大公約数〉を求める方法です。

7298 ÷ 5963 ＝ 1 … 1335
　　↙︎　　　　↙︎
5963 ÷ 1335 ＝ 4 … 623
　　↙︎　　　 ↙︎
1335 ÷ 623 ＝ 2 … 89
　　↙︎　　　↙︎
623 ÷ 89 ＝ 7 … 0

　余りが 0 になったときの「割られる数」、上の例でいうと「89」が〈7298 と 5963 の最大公約数〉です。
　これも再帰関数で書けそうです。では、どうぞ。

def gcm(a,b):
    if a%b==0:
        return b
    return gcm(b,a%b)

print(gcm(7298,5963))

　出来てしまえば、あっと驚くほどシンプルなのが、再帰関数なんですね。慣れないうちは難しいと思いますので、コツを一つ伝授しましょう。再帰関数を書くときのコツは「すでに関数が出来上がっているつもりで、それを使おうとする」姿勢（←すでに言い方が難しい？）。お楽しみください。

◇　　　　　　◇　　　　　　◇

〜 Python を手なずける 〜　
▷ 関数を定義してグラフを描くまで　　　　　　　
▷ Python で味わう、意外な確率  　　　　　　　　
▷ 再帰関数　　▷ シェルピンスキーのギャスケット