Funções Recursivas

Parte da seção Lógica e Fluxo do Journey de R da Coddy. Lição 50 de 64.

Uma função recursiva chama a si mesma em uma versão menor do problema. Ela precisa de um caso base que retorne sem chamar a si mesma, caso contrário nunca pararia:

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

Saída:

[1] 120

Cada chamada espera a chamada menor terminar: fact(3) calcula 3 * fact(2), que calcula 2 * fact(1), que retorna 1. Cada etapa deve avançar em direção ao caso-base:

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

Saída:

3 2 1 go

A recursão é adequada para dados que contêm cópias menores de si mesmos, como uma lista que contém listas. Esta função soma todos os números, independentemente da profundidade em que estejam aninhados:

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)))

Saída:

[1] 15

Uma chamada recursiva também pode dividir o problema ao meio. A busca binária examina o meio de um vetor ordenado e continua na metade que pode conter o alvo:

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))

Saída:

[1] 4
[1] NA

Desafio

Fácil

Complete count_digits(n) recursivamente. Um número menor que 10 tem 1 dígito; qualquer número maior tem um dígito a mais que n %/% 10. Não converta o número em texto.

O código fornecido lê um número inteiro n (0 ou mais) e imprime o valor retornado.

Experimente você mesmo

count_digits <- function(n) {
  # Escreva seu código aqui
  0
}

# Código de entrada/saída fornecido: mantenha-o como está
input <- suppressWarnings(readLines(file("stdin")))
cat(count_digits(as.numeric(input[1])), sep = "\n")