今回は、Rで再帰関数を作る方法を解説していきます。
R言語でも、他の言語と同様に再帰関数を書くことができますが、若干分かりづらい部分もあります。
特にvoid型の再帰関数を作るときに、ちょっとした工夫がいりました。
いろいろなタイプの再帰関数の書き方を学んでいきます。
この記事の再帰関数を含むスクリプトファイルは以下からダウンロードできます。
再帰関数
では、再帰関数の簡単な例を紹介します。
1+2+ . . . + nを計算する関数の実装を考えてみます。
for文で繰り返し計算する方法もありますが、再帰関数を使うと次のように表現できます。
1 2 3 4 5 6 7 8 9 | #簡単な例 recursiveSum <- function(n) { #1 + 2 + 3 + ... + n if (n == 0) { return(0) } else { return(n +recursiveSum(n - 1)) } } |
上記のように、関数recursiveSumの中にrecursiveSumを実行することで簡単に再帰関数が作れます。
1+2+ . . . + nを計算する関数なので、引数のnが0出ない場合 return(n +recursiveSum(n - 1))を行い、0である場合return(0)とすればよいです。
関数を実行すると次のように1からnまでの和が返ってくるのが分かります。
1 2 3 4 | > recursiveSum(2) [1] 3 > recursiveSum(10) [1] 55 |
ここから先は、再帰的なアルゴリズムをもつ関数（10進数をk進数への変換やフィボナッチ数列）の実装についてみていきます。
10進数をk進数に変換
まず最初に10進数をk進数に変換する関数を実装してみましょう。
再帰関数を用いることで、次のように書くことができます。
1 2 3 4 5 6 7 8 | ten_to_k_digits <- function(n, k) { #10進数をk進数に変換 if (n %/% k == 0) { return(n %% k) } else { return(paste0(ten_to_k_digits(n %/% k, k), n %% k)) } } |
10進数nがkで割った商が0出ない場合、return(paste0(ten_to_k_digits(n %/% k, k), n %% k))をすることで、"ten_to_k_digits(n %/% k, k)n %% k"の文字列を返すことができます。
具体例として、10を2進数に変換するとき、10 = 2 × 5 + 0であり、paste0(ten_to_k_digits(5, 2), 0)を返すことになります。最終的にn %/% k == 0となるまで、繰り返すことで、"1010"という文字列を返すことができます。
実行例は以下の通りです。
1 2 3 4 | > ten_to_k_digits(10, 2) [1] "1010" > ten_to_k_digits(689, 8) [1] "1261" |
10進数を26進数に変換（エクセルの列番号に変換）
10進数をk進数に変換で解説したものを応用すると、10進数を26進数に変換することができます。（エクセルの列番号に変換することが可能です。）
次のように、nをkで割った余りをアルファベットのベクトルLETTERSのインデックスにあてはめることで、26進数（アルファベット）に変換することができます。
1 2 3 4 5 6 7 8 | ten_to_26_digits <- function(n) { #26進数 ABCDEF if (n %/% 26 == 0) { return(LETTERS[n %% 26]) } else { return(paste0(ten_to_26_digits(n %/% 26), LETTERS[n %% 26])) } } |
次のように、10進数がエクセルの列番号に変換されているのが分かります。
1 2 3 4 | > ten_to_26_digits(55) [1] "BC" > ten_to_26_digits(265) [1] "JE" |
フィボナッチ数列
再帰関数の説明でよく登場するフィボナッチ数列についてみていきます。
wikipedia（フィボナッチ数列）のアルゴリズムを参考にすると、フィボナッチ数列は次のように表されます。
1 2 3 4 5 6 7 8 9 10 11 | fibonacciNumber <- function(n) { #フィボナッチ数列 if (n == 0) { return(0) } else if (n == 1) { return(1) } else { return(fibonacciNumber(n - 2) + fibonacciNumber(n - 1)) } } |
関数fibonacciNumberのelse文にある通り、1つ前と2つ前のフィボナッチ数列の要素の和 fibonacciNumber(n - 2) + fibonacciNumber(n - 1)を返すことでフィボナッチ数を返すことができます。
次のようにフィボナッチ数列を並べることができます。
1 2 | > sapply(seq_len(20), fibonacciNumber) [1] 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 |
フィボナッチ数列の関数を定義することができました。
注意ポイント
ただ一つだけ注意したいことがあります。 関数fibonacciNumberは、フィボナッチ数を計算する際に、n以下の全てのフィボナッチ数を計算しています。そのため、nが大きい場合\(2^n\)のオーダーで計算量が増えてしまい、実行時間が膨大になります。
以下に示すように、n-20、n=30、n=40というように大きくなるにつれて、指数関数的に計算時間が大きくなります。
1 2 3 4 5 6 7 8 9 | > for (i in c(20, 25, 30)) { + start <- Sys.time() + fibonacciNumber(i) + end <- Sys.time() + print(end - start) + } Time difference of 0.02098107 secs Time difference of 0.2438619 secs Time difference of 2.295684 secs |
これを解決する方法を次の再帰関数（グローバル変数へ値を保存する場合）で説明していきます。
再帰関数（グローバル変数へ値を保存する場合）
フィボナッチ数列の計算速度の改善
フィボナッチ数列で紹介した関数fibonacciNumberを修正していきます。
上で言った通り、関数fibonacciNumberはn以下のフィボナッチ数を全て計算しているため、計算時間が膨大になっています。
例えばn=4のフィボナッチ数を計算している場合は、n=3とn=2のフィボナッチ数も計算していることになります。これらのn=2、n=3、n=4のフィボナッチ数を保存する機能を再帰関数で表現していきます。
次のように関数の中に、フィボナッチ数列を保存するグローバル変数calculatedNumsを用意し、ローカルに再帰関数fibonacciNumberを記述することで計算量を大幅に削減することができます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | fibonacciNumber_modified <- function(n) { #キャッシュcalculatedNumsを用意 calculatedNums <- rep(NA, n + 1) fibonacciNumber <- function (n) { if (n == 0) { calculatedNums[1] <<- 0 return(0) } else if (n == 1) { calculatedNums[2] <<- 1 return(1) } else { fibTerm <- calculatedNums[c(n - 1, n)] for (i in seq_len(length(fibTerm))) { if (is.na(fibTerm[i])) { fibTerm[i] <- fibonacciNumber(n - 3 + i) calculatedNums[n - 2 + i] <<- fibTerm[i] } } return(fibTerm[1] + fibTerm[2]) } } return(fibonacciNumber(n)) } |
5行目、9行目、17行目でcalculatedNumsにすでに計算したフィボナッチ数を保存しているのが分かります。
参考
12行目のelse文では、calculatedNumsのn-1とn番目の要素であるfibTerm（1つ前と2つ前のフィボナッチ数のキャッシュ）がNAであるかないかで、フィボナッチ数を計算するかキャッシュから値を取得するかを決めています。
また、ローカルの関数内からグローバル変数にアクセスする際は、代入演算子に<<-を用います。
ポイント
<-の場合、ローカル関数fibonacciNumber内にcalculatedNumsという変数が無いためエラーが出てしまいます。<<-を用いましょう。
計算時間についてみていきましょう。先ほどの修正前の関数fibonacciNumerでは、n=40は計算量が膨大で数分待っても実行が終了しませんでした。
試しにn=100を実行してみます。
1 2 3 4 5 6 7 8 | > { + start <- Sys.time() + print(fibonacciNumber_modified(100)) + end <- Sys.time() + print(end - start) + } [1] 3.542248e+20 Time difference of 0.02598786 secs |
実行結果の通り、計算速度が改善しているのが分かります。
calculatedNumsというキャッシュへ再帰関数の値を保存していきたい場合、上のような記述が役に立ちます。ぜひ使ってください。
ベクトルの順列
最後に、再帰関数を用いて任意のベクトルの順列を求める関数の作り方の解説をします。
Rにはcombnというベクトルの組み合わせを求める関数はありますが、パッケージをインストールしないと順列の関数を使うことはできません。
上で紹介したフィボナッチ数列と同じような書き方で、簡単に順列の関数を作ることができます。
次の関数permutationがベクトルxのn個の要素から成る順列を全て求める関数です。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | permutation <- function (x, n) { permutations <- data.frame(matrix(rep(NA, n), nrow = n))[, numeric(0)] getPermutation <- function (previousX, permX, n) { if (n == 0) { permutations[, ncol(permutations) + 1] <<- permX } else { for (i in x) { getPermutation(setdiff(prevousX, i), append(i, permX), n - 1) } } } getPermutation(x, NULL, n) return(permutations) } |
n行0列のデータフレームpermutationsを最初に宣言し、ローカル関数getPermutation内でpermutationsに順列を逐次格納していきます。
5行目でgetPermutationの引数nが0になったら、permutationsの新しい列に順列permXを代入しているのが分かります。
実行結果は以下の通りです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | > permutation(letters[1 : 4], 2) V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V14 V15 V16 1 a b c d a b c d a b c d a b c d 2 a a a a b b b b c c c c d d d d > permutation(c("red", "green", "blue"), 3) V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V14 V15 V16 V17 V18 V19 1 red green blue red green blue red green blue red green blue red green blue red green blue red 2 red red red green green green blue blue blue red red red green green green blue blue blue red 3 red red red red red red red red red green green green green green green green green green blue V20 V21 V22 V23 V24 V25 V26 V27 1 green blue red green blue red green blue 2 red red green green green blue blue blue 3 blue blue blue blue blue blue blue blue |
ベクトルxのnまでの順列が全て出力されているのが分かります。
まとめ
R言語で再帰関数の作り方や例を紹介しました。
ここで紹介した例を用いれば、だいたいの再帰的なアルゴリズムを表現することが可能です。
ぜひ参考にしてください。
