再帰関数について【PHP】【Python】

前回の記事で少し触れた再帰関数についてまとめていきたいと思います。

再帰関数とは

自分自身を呼び出す関数のことを再帰関数と言います。
自分自身を呼び出すとはどういうことなのか感じる方もいると思いますが、ソースを読んだり、
ソースを書いてみるとなんとなくイメージができると思うので実際にやっていきましょう。

例題1：階乗の計算

標準入力

入力Nの階乗を求めます。
再帰関数を使用しない場合は下記のようになります。

処理手順

for文を使用し、$i = 1がNになるまで掛け続ける

実装例

<?php

$n = trim(fgets(STDIN));

$answer = 1;
for ($i = 1; $i <= $n; $i++) {
  $answer *= $i;
}

echo $answer;

Python

n = int(input())

answer = 1
for i in range(1, n + 1):
  answer *= i

print(answer)

では再帰関数を使用する場合を考えます。
再帰関数では関数を定義するため、条件を洗い出します。
下記が処理条件になります。

処理条件

Nが1の場合には1を返す
Nが2以上の場合には（N - 1の計算結果） * Nを返す

処理イメージ

※ 関数名をfactorial()とし、N = 5とします。

factorial(5)を呼ぶ
factorial(4)が呼ばれる
factorial(3)が呼ばれる
factorial(2)が呼ばれる
factorial(1)が呼ばれ、Nが1なので1を返す
factorial(2)でfactorial(1)で返ってきた1と2を掛け、計算結果を返す
factorial(3)でfactorial(2)で返ってきた2と3を掛け、計算結果を返す
factorial(4)でfactorial(3)で返ってきた6と4を掛け、計算結果を返す
factorial(5)でfactorial(4)で返ってきた24と5を掛け、計算結果を返す

実装は下記のようになります。

実装例

<?php

function factorial($n)
{
  if ($n === 1) return 1;
  return factorial($n - 1) * $n;
}

$n = trim(fgets(STDIN));
echo factorial($n);

Python

def factorial(n):
  if n == 1:
    return 1

  return factorial(n - 1) * n

n = int(input())
print(factorial(n))

補足

ここで再帰関数を実装する際の注意点として「ベースケース」というものを定義する必要があります。
上記の再帰関数では

PHPではif ($n === 1) return 1;の箇所
Pythonではif n == 1:の箇所

この場合分けを定義しない場合には処理が終わらなくなってしまうので注意が必要です。

例題2：フィボナッチ数列

ここで一旦、漸化式についてまとめたいと思います。
漸化式というのは、数列において前項の計算結果からその項の値を求める規則のことです。
簡単に説明すると前の計算結果を用いて新しい計算結果を求める的な感じです。
例題1の階乗の例でいうところの処理条件のところになります。

ではフィボナッチ数列についてやっていきたいと思いますが下記が漸化式になります。

a1 = 1, a2 = 1
an - 1 + an - 2

つまり、最初の項と2項目までは1でそれ以降は、前の2つの項を足した値になるということになります。

実装例

標準入力

Nのフィボナッチ数列を求めます。

<?php

function fibonacci($n)
{
  if ($n <= 2) return 1;
  return fibonacci($n - 1) + fibonacci($n - 2);
}

$n = trim(fgets(STDIN));
print(fibonacci($n));

Python

def fibonacci(n):
  if n <= 2:
    return 1

  return fibonacci(n - 1) + fibonacci(n - 2)

n = int(input())
print(fibonacci(n))

最後に

再帰関数は、処理イメージを持つのがやや複雑な部分がありますが、
地道に処理を追っていけば理解できるものだと思っています。
また、漸化式を応用した動的計画法についてもまとめていけたらと考えています。

ryubloblog’s diary

宮城県の仙台で働くプログラマーです。