Python プログラミング

再帰とは何か？Python3の簡単な例で再帰の仕組みを学ぶ

エンジニアの知り合いに再帰についてちゃんと勉強しておいた方がいいというアドバイスをもらいました。

ということで、今回はPythonで再帰を使った簡単なコードを書いてみることにします。

そもそも再帰とは何か？

再帰とは、再帰関数とか再帰処理とも呼ばれるプログラミングのテクニックのこと。

具体的にどういうことをするのかというと、関数が自分自身を呼び出して同じ処理を何度も繰り返す。ということらしい。

正直これだけ聞いても再帰がどんなものか？どんなことができるのか？ということがいまいち分からない・・・

そもそも自分みたいな非エンジニアの素人からすれば、同じ処理を繰り返すならループでいいじゃん。って思ってしまいます。

プログラミングの勉強をしていると、こんな感じになんかよく分からない。みたいなことに出くわすことがあります。僕は、そういう時にはとりあえずシンプルだけどちゃんと動くコードを書いてみることにしています。

で、それが理解できたらちょっとずつ機能を付け加えてカスタマイズしていく。そんな風にしていくと理解がしやすいと思います。

ということで、今回も簡単なコードを書いてみます。

再帰でカウントダウンする

まずは、引数に渡した数字から0までをカウントダウンして表示するだけの関数を作ってみます。 

def count_down(i):
'''引数で受け取った数字から0までをカウントダウンして表示する'''

    print(i)     #①
    if i <= 0:     #②
        pass
    else: 
        count_down(i-1)     #③

count_down(3)     #④

それではコード中身を見ていきます。

作ったのはcount_downという関数です。

引数iに整数を渡すと①でその値を表示します。

次にif文を用意します。コードの②の部分です。iが0以下ならpassで何も実行しません。

そうでなければ、iから1を引いた値を引数にして再びcount_downを呼び出します。③の部分です。この部分が再帰です。

関数count_downの中でconut_downを使っています。つまり、関数が自分自信を呼び出す処理になっています。

④は初めにcount_downを呼び出す処理です。
引数に3を取っているので、このコードを実行すると3、2、1、0と順に表示されます。

再帰の注意点1

このコードには2つのポイントがあります。

1つ目は、ifでiが0以下の場合の処理が記述してあること。

2つ目は、再帰でcount_downを呼び出す時に引数をi-1としていることです。

この2つの処理がないとcount_downは無限ループに陥ってしまいます。

再帰では、関数内で自分自信を呼び出して同じ処理を繰り返すため、ちゃんと再帰から抜ける処理を書かないと無限ループになってしまう危険があります。

再帰を使って階乗を求める

もう1つ簡単なプログラムを作ってみます。

今度は、引数で渡した数の階乗を求めるプログラムです。階乗というのは、ある数から1までの積を求めることです。

数学では、x! と表します。
4! であれば、4×3×2×1=24 となります。

これをPythonで再帰を使って書いてみます。

def factorial(x):     #①
    if x == 1:     #②
        return 1
    else:
        return x * factorial(x-1)     #③

print(factorial(3))     #④

factorialのコードの解説

①で関数factorial()を定義します。factorialというのは英語で階乗のことです。factorial()は、引数で受け取るxの階乗を求める関数です。

②ではifを使って引数xが1の時の処理を書いています。引数xが1の時、factorial()は1を返します。

③は引数xが1以外の時の処理なのでelseの中に書いています。この時、factorial()は引数xにfactorial(x-1)の戻り値を掛けた値を返します。

この辺の動きは少し分かりにくいですよね？
この後もうちょっと細かく見ていくことにします。

④は、引数に3を取ったfactorial()の結果を表示するコードです。引数が3なので3! = 3×2×1 を求めることになります。

factorial(3)の処理の具体的な流れ

それではfactorial(3)の処理の流れを順を追って見ていきましょう。

1.まずは引数に3を渡してfactorial()を呼び出します。

2.factorial()の中では、if文を使って受け取った引数xの値によって処理を分岐します。今のxは3なのでelseの処理が行われます。

3.elseの処理によって、factorial(3)はx * facrorial(x-1)を返します。つまり、3 * factorial(2)を返すことになります。しかし、このまま3 * factorial(2)を返すのではなく、先にfactorial(2)の結果を求めて、その結果に3を掛けた値を返します。

factorial(2)を求めてる間、factorial(3)についてはメモリに保存され、factorial(2)の結果がでるまで保留になります。

4.factorial(2)も引数xが1ではないのでelseの処理が行われます。factorial(2)の戻り値は、2 * factorial(1)となりますが、これもfactorial(1)の結果が出るまで保留になります。

5.factorial(1)は、引数xが1なので1を返します。

6.factorial(1)から結果が戻ってきたのでfactorial(2)の結果を出すことができます。factorial(2)の戻り値は2 * factorial(1)だったので、2 * 1 、つまり2を返します。

7.factorial(2)の結果が返ってきたので、同じようにfactorial(3)の結果を出すことができます。factorial(3)の戻り値は、3 * factorial(2) だったので 3 * 2 、つまり6ということになります。

ここまでの流れをまとめると、

factorial(3)を呼び出す
↓
factorial(3) = 3 * factorial(2)
↓
factorial(2)を呼び出す
↓
factorial(2) = 2 * factorial(1)
↓
factorial(1)を呼び出す
↓
factorial(1) = 1
↓
factorial(2) = 2 * 1 = 2
↓
factorial(3) = 3 * 2 = 6

以上がfactorial(3)が6になるまでの流れでした。

ちなみに、Pythonではわざわざ再帰を使わなくてもmathモジュールを使えば簡単に階乗を求めることができます。

>>> import math
>>> math.factorial(3)
6

再帰の注意点2

factorial()の具体的な流れを見た際に、再帰でfactorial(x - 1)を呼び出してる時はfactorial(x)は保留になっていて、メモリに保存されてると書きました。これが再帰の注意点2です。

今回のfactorial(3)のように再帰の回数が少ない場合は問題ありませんが、再帰の数が多くなると多くのメモリを消費することになります。場合によってはプログラムが途中で止まったりしてしまうこともあるので注意が必要です。

そういう場合はループを使ったり、Pythonであればジェネレータを使うなどしてパフォーマンスを改善することができます。

また、メモリを使いすぎなように工夫された末尾再帰という方法もありす。これについては、このブログでもいずれ取り上げようと思います。

再帰のメリットは？

ここまで再帰について学んできましたが、少し難しいと思った人がいるかもしれません。僕も初めは難しいと思いました。というか今でも思います…。でも、少しずつでも使っていれば、きっとそのうち慣れるだろうなと思ってます。

再帰ってのは慣れるとループを使うよりもシンプルにコードが書けることが多いそうです。そのため色々な所で使われています。だから、ちゃんと読めるようになっておかなければいけないのです。(知人にそう言われました。)

再帰には、メモリを大量に使用してコンピュータのパフォーマンスが悪化してしまうこともあるというデメリットがあります。しかし、一方でシンプルで分かりやすいコードを書くことができるのでプログラマのパフォーマンスは上がると言われているそうです。

再帰のメリットはまさにこれ。再帰を使うとエレガントなコードが書ける！

まとめ

• 再帰を使う時は無限ループにらならないように気をつける。
• 再帰を使うとパフォーマンスが悪化してしまうことがある。その場合はループを使うなどす。
• 再帰は色々なところで使われているので、読めるようにしておいた方がいい。
• 再帰を使うとエレガントなコードが書ける。