Python入門：再帰関数についての解説。関数が自分自身を呼び出すとは？

今回のPython初心者向けの文法入門解説は再帰関数と言われる関数の使い方についてです。

再帰関数とは、ある関数があって、その処理の中で自分自身を呼び出して使うことがある関数です。

使い方・書き方

さてまず大雑把ではありますが、再帰関数の構文（？）というか書き方を見ましょう。次のようになります。

#再帰関数Aの定義・宣言
def A(x):
    処理を終了する条件とその場合の処理 #1

    return 自分自身（A） #2

A(引数)

最初のdef〜は関数を定義・宣言しているだけですが、その中身は大きく2つのパーツから構成されます。それは、

• 処理を終了する条件とその場合の処理 #1
• return 自分自身を使った処理 #2

です。

実際上一番重要なのは実は#1のほうでしょうか。

これは再帰処理を終了する条件を設定するパーツですが、もしこれがなければ無限に処理が実行され続けてしまい、無限ループのような状態になります。自分自身を永遠に呼び続け、実行し続けるという状態になってしまうのです。

これだけではよくわからないので、さっそく簡単なコード例を見てみましょう。

具体例

正の整数を100まで足したらいくらになるか？というものを計算するプログラムが次になります。これは再帰関数の説明でよく使われるプログラムでしょう。

def sum(n):
    #再帰終了条件の設定
    if n==0:
        return 0
    #再帰処理
    return n + sum(n-1)

print(sum(100)) 

ここで見ていただきたいのは、次の箇所です。

return n + sum(n-1)

最初に関数sum()を定義しましたが、そのsum()自身の中に、また自分自身であるsum()が使われていて、呼び出されています。

ちなみに、今回の計算は暗算でも計算できまして次のように考えます。

(1+100)+(2+99)+(3+98)+(4+97)・・・・+(49+52)+(50+51)=101×50=5050

足して101になるセットを50個作るという考え方です。

処理の流れの解説

まずこの再帰関数の大まかな処理のイラストを見てください。次の画像です。

まず、

print(sum(100)) 

このように引数に100が設定されてsum関数（）が呼び出され実行されます。このとき、

def sum(n):
    #再帰終了条件
    if n==0:
        return 0
    #再帰処理
    return n + sum(n-1)

この部分において、今、変数nは100ですから0ではありません。

したがって、再帰終了条件のif文は無視され、再帰処理の部分が実行されます。

return 100 + sum(99)

このような処理が実行されるわけです。その結果、

「100」 ＋「 sum(99)の実行結果」

がreturnによって、sum()自身に返されます。

しかし、sum(99)の実行結果は、

return 99 + sum(98)

となります。この結果、つまり、「99 + sum(98)」がまたsum()に返されます。この時点で、

100 ＋ 99 + sum(98)となるわけですね。

そしてsum(98)は、やはり、

return 98 + sum(97)

となります。これがまたsum()自身に返され、

100 + 99 + 98 + sum(97)

となります。

あとはnが0になるまでそのような処理が続けられます。

そして、if文中の

n==0

という条件が充たされたときに、再帰処理が終了します。もしこれがなければ、永遠に足し算を続けてしまい、プログラムが止まらなくなります。そうなるとプログラムを強制終了させる必要が出てきます。

よって、再帰関数を使うときは必ず再帰処理を終了する条件を書くように注意しましょう。

さて、以上より、

100 + 99 + 98 + 97 + 96 +････････+3+2+1+0

となり、その答え5050が出力されます。

for文を使う場合と比べたときのメリット

再帰関数については、再帰関数というものを使わなくてもfor文を使っても同じ処理を実現できることが多いです。

しかしfor文を使うとその内部で場合分けが多くなり、コードが複雑になってしまうことがあります。そ場合に再帰関数を使うとよりシンプルに書けるというメリットがあります。