Я хотел сделать серию статей о том, как справляться с типичными техническими проблемами, с которыми разработчики могут столкнуться во время интервью.
Сегодня я хотел взглянуть на рекурсию.
Согласно Википедии, если использовать рекурсию в отношении информатики, это «метод решения проблемы, решение которого зависит от решений более мелких экземпляров той же проблемы». Рекурсия не всегда необходима и часто излишня для поиска ответа. Тем не менее рекурсии не существовало бы, если бы она не пригодилась для решения некоторых задач.
Прежде чем мы начнем, я хочу дать краткое определение факториала. Факториал — это произведение всех положительных целых чисел, меньших или равных исходному числу. Обозначается как n! гдеnявляется представлением числа. Некоторые примеры:
3! = 6 //because 1 * 2 * 3 = 6 5! = 120 //because 1 * 2 * 3 * 4 * 5 = 120
Вам нравится факториал? Давайте двигаться дальше.
Проблема сегодня состоит в том, чтобы использовать рекурсию для нахождения факториала любого заданного числа.
Бывший. Вот решение, которое я нашел без использования рекурсии:
const recursiveFactorial = (number, array, total) => {
let newArray = [];
let i;
for (i = 1; i <= number; i++){
newArray.push(i)
}
var total = 1;
newArray.forEach(num => {
total = num * total
})
}
recursiveFactorial(10)
Код также можно найти здесь, в этом repl.
Но если задача состоит в том, чтобы использовать рекурсию для поиска решения, давайте проведем рефакторинг, чтобы использовать ее.
Для этой проблемы есть две рекурсивные функции, которые будут работать вместе, чтобы найти решение.
Кроме того, если вы хотите проверить окончательное решение и в каком направлении движется код, вы можете проверить это repl.
Мы начнем с создания двух функций. Функция buildArray будет работать до своего базового случая, а затем передавать свою информацию в returnFactorial, которая будет работать до своего собственного базового случая и возвращать наш окончательный факториал. Давайте начнем с создания некоторых фреймворков:
const buildArray = (num) => {
if () {
} else {
}
}
const returnFactorial = () => {
if () {
} else {
}
}
buildArray(5)
Выглядит хорошо отсюда, но что мы сделали? Мы создали две функции с синтаксисом ES6, которые имеют операторы if..else с именами buildArray и returnFactorial. Затем мы вызвали buildArray с целым числом 5, и это будет число, факториал которого мы ищем. Мы можем добавить некоторые параметры по мере продвижения вперед, но эта отправная точка кажется хорошей.
Далее мы собираемся сделать базовый случай. Базовый случай — это условие, над которым работает эта функция. Он принадлежит части if нашего оператора if..else. Поскольку мы строим массив, давайте запустим условие при построении массива. Массив, который нам нужен, будет включать все положительные целые числа, которые меньше или равны исходному числу.
Давайте на минутку подумаем и напишем код:
const buildArray = (num) => {
if (num === 0) {
returnFactorial() //we will want to pass this fn an array
} else {
let arrayOfNums = [];
arrayOfNums.push(num); //this will only get the original number
//we want to call buildArray here again and have it take
//a parameter for an array
}
}
const returnFactorial = () => {
if () {
} else {
}
}
buildArray(5)
Что только что произошло? Мы добавили базовый вариант, в котором говорится, что если num === 0, то переходим к этой другой функции с именем returnFactorial. В настоящее время эта функция не принимает никаких параметров, но ей нужно будет использовать массив, созданный в функции buildArray.
Мы также добавили в else часть. Сначала мы объявили arrayOfNums и присвоили его пустому массиву. Затем мы использовали метод прототипа массива .push(), чтобы мы могли поместить исходное число в массив.
Этого недостаточно. Теперь нам нужно снова вызвать buildArray, чтобы добавить в наш массив (и сделать эту функцию рекурсивной). Но подождите, наша функция buildArray не принимает массивы. Нам нужно добавить этот параметр в функцию.
Добавим некоторые изменения:
const buildArray = (num, array) => { //added array param
if (num === 0) {
returnFactorial(array) //added array arg
} else {
let arrayOfNums = [];
arrayOfNums.push(num);
buildArray(???, arrayOfNums) //called buildArray, but need num
}
}
const returnFactorial = (array) => { //added array param
if () {
} else {
}
}
buildArray(5, []) //added array arg
Хорошо, выглядишь лучше. Мы добавили array в качестве параметра или аргумента в нескольких местах, и это кажется правильным. Однако я заметил одну вещь: когда мы вызываем buildArray без нового номера. Нам нужно установить новый номер, чтобы buildArray мог добавить его в коллекцию.
Я думаю, что это должно работать:
const buildArray = (num, array) => {
if (num === 0) {
returnFactorial(array)
} else {
let arrayOfNums = [];
arrayOfNums.push(num);
//changes in next two lines
let newNumber = num - 1
buildArray(newNumber, arrayOfNums)
}
}
const returnFactorial = (array) => {
if () {
} else {
}
}
buildArray(5, [])
Мы добавили новую переменную с именем newNumber. Это число — просто старое число минус один. Это будет продолжаться, в случае примера, от 5 и добавления его к массиву до 1. Когда 1 добавляется к массиву, newNumber будет равен нулю, и базовый случай будет выполнен, отправляя нас к следующей функции.
Кстати, это 1000% можно было бы сделать с помощью цикла for, но я хочу использовать рекурсию.
Поздравляю! Мы сделали нашу первую рекурсивную функцию. Далее мы хотим сделать второй! Давайте посмотрим, где мы находимся, и построим для returnFactorial :
const buildArray = (num, array) => {
if (num === 0) {
returnFactorial(array)
} else {
let arrayOfNums = [];
arrayOfNums.push(num);
let newNumber = num - 1
buildArray(newNumber, arrayOfNums)
}
}
//when returnFactorial is called first the array it is passed is
// [5,4,3,2,1]
const returnFactorial = (array) => {
if (array.length === 0) {
return ??? //we need a total number to add and return here
} else {
console.log(array)
}
}
buildArray(5, [])
Здорово. Теперь у нас есть массив, включающий все положительные целые числа, которые меньше или равны пяти, и он передается в функцию returnFactorial. Проблема возникает, когда мы добираемся до нашего базового случая. Что возвращаем? Похоже, у этой функции должен быть еще один параметр, чтобы мы могли получить окончательное число. Мы будем использовать число 1, потому что 0! === 1 .
Давайте добавим некоторые параметры и аргументы по мере необходимости:
const buildArray = (num, array) => {
if (num === 0) {
returnFactorial(array, 1) //add arg here
} else {
let arrayOfNums = [];
arrayOfNums.push(num);
let newNumber = num - 1
buildArray(newNumber, arrayOfNums)
}
}
const returnFactorial = (array, factorialTotal) => { //add param
if (array.length === 0) {
return factorialTotal
} else {
console.log(array)
}
}
buildArray(5, [])
Потрясающий. Теперь у нас есть базовый вариант, к которому мы хотели бы добраться, но пока нет реального способа добраться туда, поскольку вторая функция — это только запись массива в консоль. Это еще даже не рекурсивная функция.
Мы можем это изменить:
const buildArray = (num, array) => {
if (num === 0) {
returnFactorial(array, 1)
} else {
let arrayOfNums = [];
arrayOfNums.push(num);
let newNumber = num - 1
buildArray(newNumber, arrayOfNums)
}
}
const returnFactorial = (array, factorialTotal) => {
if (array.length === 0) {
return factorialTotal
} else {
returnFactorial(???, ???) //wait, what goes here
}
}
buildArray(5, [])
Теперь он готов к рекурсии. Проблема в том, что нам нужно манипулировать массивом, и нам нужно каким-то образом изменить сумму. Как?
Для начала мы хотим использовать метод прототипа массива .shift(). Этот метод удаляет первый элемент и возвращает его. Мы зафиксируем это возвращенное число в переменной
Кроме того, .shift() навсегда изменит наш массив, но на самом деле это работает в нашу пользу.
Проверьте это:
const buildArray = (num, array) => {
if (num === 0) {
returnFactorial(array, 1)
} else {
let arrayOfNums = [];
arrayOfNums.push(num);
let newNumber = num - 1
buildArray(newNumber, arrayOfNums)
}
}
const returnFactorial = (array, factorialTotal) => {
if (array.length === 0) {
return factorialTotal
} else {
//changes in next two lines
let shiftedNumber = array.shift()
let newTotal = shiftedNumber * factorialTotal
returnFactorial(array, newTotal)
}
}
buildArray(5, [])
Это работает. Это даст нам факториал любого числа.
Последние добавления, которые мы сделали, заключаются в том, чтобы зафиксировать число, которое мы извлекли из массива, в переменную, известную как shiftedNumber. Затем мы умножили это число на factorialTotal и записали результат в переменную с именем newTotal. Наконец, мы можем снова вызвать метод с array, который был постоянно смещен, и с нашей переменной newTotal. Когда все элементы будут перемещены из массива, базовый случай будет выполнен, и будет возвращен factorialTotal.
Спасибо за чтение! Вот, опять конечный результат в репле и конечный код без примечаний:
const buildArray = (num, array) => {
if (num === 0) {
returnFactorial(array, 1)
} else {
let arrayOfNums = [];
arrayOfNums.push(num);
let newNumber = num - 1
buildArray(newNumber, arrayOfNums)
}
}
const returnFactorial = (array, factorialTotal) => {
if (array.length === 0) {
return factorialTotal
} else {
let shiftedNumber = array.shift()
let newTotal = shiftedNumber * factorialTotal
returnFactorial(array, newTotal)
}
}
buildArray(5, [])
