Rubyで再帰関数について軽くまとめ

再帰関数について軽くまとめてみます、今回はRubyで書きます。

再帰関数とは

関数Aの中で同じ関数Aを使う処理を行う関数のことです。

例：

def A(num)
  A(5)
end

↑みたいに普通に呼び出すだけだと、Aが呼んだAが呼んだAが呼んだAが…と無限ループになってメモリを食い潰します。

よくある例は階乗を求める関数です。

def kaijo(num)
  return 1 if num.zero?
  num * kaijo(num - 1)
end

# 三項演算子ver
def kaijo(num)
  num.zero? ? 1 : num * kaijo(num - 1)
end

kaijo(3)とした場合、kaijo(2)、kaijo(1)と呼ばれていき、最終的にkaijo(0)が呼び出され、1が返却されることで再帰は終わります。よって無限ループは起こりません。

使い時

使い所が難しいのですが、階層になっているデータを扱うときに用いると便利なようです。主に木構造と呼ばれるものです。

例

というわけで試しに配列の入れ子を作ってみます。

[1, [1, 2, [6, 3, 2], 2], 3, [2, 4]]

で、これらをすべて足し合わせてみます。

分岐で作った場合

まずは無理やり分岐で（悪い例です）

def nested_array_sum(arrayOrNum)
  sum = 0
  arrayOrNum.each do |tmp|
    if tmp.instance_of?(Integer)
      sum += tmp
    elsif tmp.instance_of?(Array)
      arrayOrNum.each do |tmp|
        if tmp.instance_of?(Integer)
          sum += tmp
        elsif tmp.instance_of?(Array)
          arrayOrNum.each do |tmp|
            sum += tmp
          end
        end
      end
    end
  end
  sum
end

puts  nested_array_sum([1, [1, 2, [6, 3, 2], 2], 3, [2, 4]])
=> 26

データのネストの階層がソースのネストの階層と連動するようになってしまいました。とてつもなく読みにくい上に、これだとデータの階層が深くなるたびにこの関数を修正する必要があります。

再帰関数で作った場合

では次は再帰関数で。

def nested_array_sum(array_or_num)
  if array_or_num.instance_of?(Array)
    array_or_num.reduce(0) do |sum, tmp|
      sum + nested_array_sum(tmp)
    end
  else
    array_or_num
  end
end

puts array_sum([1, [1, 2, [6, 3, 2], 2], 3, [2, 4]])
=> 26

引数が配列か数字か確認し、配列ならループを回しつつ再帰的に関数を呼ぶ構造になっています。

先程と比べてネストも浅くスッキリした上に、階層が深くなっても浅くても問題なく動くようになりました。

まとめ

今回は例として入れ子の配列を再帰関数で足してみました。デメリットとしてメモリの消費が大きいというのがよくあげられますが、数百階層とかにでもならない限りは大丈夫だと思います。

木構造のデータを触る際には再帰による処理も候補に入れつつ考えたいと思います。

おまけ

ちなみにRubyにはArray#flattenという配列を一次元にする便利メソッドがあります。

[1, [1, 2, [6, 3, 2], 2], 3, [2, 4]].flatten.sum
=> 26

上記のようにこれを使うと一撃でできるのですが、勉強にならないため再帰で作ってみました。

コーディングを支える技術 ~成り立ちから学ぶプログラミング作法 (WEB+DB PRESS plus)