再帰関数

CoddyのRジャーニー「ロジックとフロー」セクションの一部。レッスン 50/64。

再帰関数は、問題をより小さくしたものに対して自分自身を呼び出します。自分自身を呼び出さずに戻る基底ケースが必要です。そうでなければ、決して停止しません。

fact <- function(n) {
  if (n <= 1) return(1)
  n * fact(n - 1)
}
print(fact(5))

出力:

[1] 120

各呼び出しは、より小さい呼び出しが完了するまで待機します。fact(3)は3 * fact(2)を計算し、これは2 * fact(1)を計算し、1を返します。すべてのステップはベースケースに近づかなければなりません：

count_down <- function(n) {
  if (n == 0) {
    cat("go\n")
    return(invisible(NULL))
  }
  cat(n, "")
  count_down(n - 1)
}
count_down(3)

出力：

3 2 1 go

再帰は、リストを保持するリストのように、自分自身のより小さなコピーを含むデータに適しています。この関数は、どれだけ深くネストされていても、すべての数値を加算します。

deep_sum <- function(x) {
  if (is.numeric(x)) return(sum(x))
  total <- 0
  for (item in x) total <- total + deep_sum(item)
  total
}
print(deep_sum(list(1, list(2, 3), list(list(4)), 5)))

出力:

[1] 15

再帰呼び出しでは、問題を半分に分割することもできます。二分探索はソート済みのベクトルの中央を調べ、対象を含む可能性のある半分で処理を続けます。

find <- function(v, target, lo = 1, hi = length(v)) {
  if (lo > hi) return(NA)
  mid <- (lo + hi) %/% 2
  if (v[mid] == target) return(mid)
  if (v[mid] < target) find(v, target, mid + 1, hi) else find(v, target, lo, mid - 1)
}
print(find(c(2, 5, 8, 12, 19), 12))
print(find(c(2, 5, 8, 12, 19), 7))

出力：

[1] 4
[1] NA

チャレンジ

簡単

count_digits(n)を再帰的に完成させてください。10未満の数は1桁で、それより大きい数はn %/% 10より1桁多くなります。数値をテキストに変換しないでください。

提供されたコードは整数n（0以上）を読み取り、返された値を出力します。

自分で試してみよう

count_digits <- function(n) {
  # ここにコードを書いてください
  0
}

# 提供された入出力コード：そのままにしておいてください
input <- suppressWarnings(readLines(file("stdin")))
cat(count_digits(as.numeric(input[1])), sep = "\n")