Понимание рекурсии на практике

На прошлой неделе мне задали несколько технических вопросов, на которые я должен был ответить, чтобы получить потрясающую возможность. Я мог использовать любой язык. Я выбрал Ruby, потому что я изучил Ruby on Rails для серверной части и решил, что мне будет проще манипулировать данными с помощью этого языка. (Javascript не был для меня естественным во время фиктивного технического собеседования. Я бы хотел, чтобы Javascript был отключен для алгоритмов. Или Python. Впрочем, это задача для другого дня.)

В итоге я использовал рекурсию. Возможно, это не лучший способ решить вопрос, но это произошло. Это пробудило во мне любопытство к рекурсии, поэтому я хочу вернуться к этой теме, а затем поговорить о последовательности Фибоначчи с точки зрения рекурсии.

Что такое рекурсия?

Статья о рекурсии в Википедии может ответить так: Большинство компьютерных «языков программирования поддерживают рекурсию, позволяя функции вызывать себя из своего собственного кода».

По моим собственным словам, код функции или метода использует сам себя. Вы можете найти имя функции внутри ее кода и используемой функции.

Пожалуйста, прочитайте эту статью для получения дополнительной информации:

(Спасибо этой статье на Medium за шутку)

Мое использование рекурсии с высокими ставками

Один из этих вопросов связан с созданием метода для декодирования строки.

Правило таково: k[encoded_string] где k — целое положительное число, а строка в скобках повторяется k раз.

Входы "3[cd]" и "2[d2[c]]" выведут "cdcdcd" и "dccdcc" соответственно.

Вот мой подход к такого рода вопросам:

1. Запишите псевдокод.
2. Попробуйте написать код.
3. Исследуйте методы и проверьте, на что способен язык.
4. Дважды проверьте, делает ли он то, что вы ожидаете. (короткая обратная связь)
5. Не стесняйтесь начинать сначала, пока это не сработает.
6. Дважды проверьте все в конце.

Итак, давайте перейдем к моему коду.

def decode_string(s)
  results_arr = []
  #turn string into array of char. reverse array and make numbers integers instead of strings. numbers are needed to multiply
  num_array = s.chars.map do |char|
    if char.to_i != 0
      char.to_i
    else
      char
    end
  end.reverse
  #find the innermost and multiply by number. combine with the rest of the array
  num_array.each_with_index do |element, index|
    if element == "["
      multiplied = num_array[0..index] * num_array[index + 1]
      results_arr = multiplied.join("").delete("[]").split("") + num_array[index + 2...num_array.length]
      break
    end
  end
  braced_results_str = results_arr.join("").reverse
  decoded = braced_results_str.delete("[]")
end

1. Я превращаю строку в массив одиночных символов. Числа становятся реальными числами, поэтому я могу умножать и повторять символы позже. (Реверс тоже необходим!) "a" * 3 возвращает "aaa"
2. Следующий шаг включает в себя просмотр этого массива и поиск числа для умножения. Как только я нахожу это число, я умножаю. Затем код объединяет только что перемноженный массив и остальную часть массива. Код, наконец, превращает конкатенированный массив обратно в строку. (Нужны мелочи, чтобы все выглядело красиво, но для decode_string("3[cd]") все как на картинке идеально)
3. Это не относится к decode_string("2[d2[c]]"). Возвращаемое значение: "2dcc"
4. Перед последней строкой puts braced_results_str дает подсказку, которая приводит к использованию рекурсии. Код имеет "2[dcc" перед последней строкой.
5. Здесь можно использовать условную рекурсию, потому что она имеет [, что я проверяю перед умножением. (Интересно, есть ли более оптимизированный способ сделать это. Однако у меня было мало времени.)

def decode_string(s)
  ...
  #check if there is still a number. recursion
  if braced_results_str.to_i != 0
    braced_results_str = decode_string(braced_results_str)
  end
  decoded = braced_results_str.delete("[]")
end

Основная концепция, найденная здесь, такова: коду с рекурсией нужен выход из самого себя. (обычно базовый случай) В противном случае я мог бы увидеть, как это застревает в бесконечном цикле, пока не сломается.

Последовательность Фибоначчи

Для моего фиктивного интервью последовательность Фибоначчи стала моим домашним заданием:

// given a number n return the value at index n of the fibonacci sequence using recursion:
// 0,1,1,2,3,5,8,13 given n = 6, return 5, if n = 7, return 8 etc.

Момент озарения поразил меня довольно быстро после использования рекурсии в более раннем вопросе и беглого просмотра последовательности Фибоначчи в Википедии, особенно этой части:

Вот мой код для Фибоначчи в Ruby:

def fibonacci(n)
  if n == 0
    return 0
  elsif n == 1
    return 1
  else
    recursion = fibonacci(n-1) + fibonacci(n-2)
    return recursion
  end
end

Вот мой код для Фибоначчи в Javascript:

const fibonacci = n => {
  if (n===0) {
    return 0
  } else if (n===1) {
    return 1
  } else {
    let recursion = fibonacci(n-1) + fibonacci(n-2)
    return recursion
  }
}

Идея в том, что первые два числа последовательности автоматически появляются. Семена дают ему выход из метода и функции. В следующей части используется рекурсия для работы с большими индексами.

Рекурсия — еще один инструмент в моем наборе инструментов. Я должен использовать его с умом.