再帰って?ループとの違いは?
再帰を初めて学ぶとき、なんだかよく分からなくなりませんか?
私もその一人です。RecursionというCSを学べるサービスで、CS中級コースにこいつが出てきます。
再帰とは何なのか、for文とかwhile文とかのループ処理を記述する構文と何が違うのかを解説していきます。
今回の記事は、Pythonを使って解説します。
再帰とは
再帰とは、関数を実行しているときに関数自身を繰り返し呼び出す処理のことです。
再帰が行われる関数を、再帰関数と呼びます。
例として、10までカウントするcountToTen関数があるとします。
def countToTen(a):
if a > 10:
return "stop"
print(a)
return countToTen(a+1)
print(countToTen(0))
引数を 0 として実行してみると...
0
1
2
3
4
5
6
7
8
9
10
stop
このように出力されました。何が起こっているのかというと、countToTen関数を実行しているとき、return文で自分自身(countToTen関数)を呼び出しています。
この時、引数として a+1 を指定しており、最初の引数が 0 であれば、次は 1 、次は 2 という風に条件が真となるまでループします。
a が 10 より大きくなったとき、stop と出力されて終了します。(ここでは分かりやすくするため関数内にprint文を挿入しています)
if a < 10:
return "stop"
上記のように、ループを終了させる処理をベースケースといいます。これがない場合は、無限ループに陥る可能性が高いので、ベースケースがあるか、正常に動作するかを意識する必要があります。
for文・while文などの違い
for文・while文とかだって、ループ処理を行います。でもちゃんとした違いがあります。
再帰は自分自身(関数)を呼び出す処理であり、for文・while文などのループは、単に処理を繰り返す処理です。自分自身を呼び出して処理を繰り返しているわけではありません。
for文の例を見てみましょう。
for i in range(11):
print(i)
ここでは、 i を出力する、という単なる処理を11回繰り返しているだけです。
0
1
2
3
4
5
6
7
8
9
10
なので、違いは分かりやすいと思います。
終わりに
追記、編集箇所があればそれもアップします。
参考
Discussion