Привет! Мы вернулись еще на одну неделю, чтобы поговорить о некоторых темах функционального программирования. Если вы пропустили на прошлой неделе, вы можете вернуться и прочитать здесь. На этой неделе собирались затронуть одно очень важное понятие, рекурсию.
На прошлой неделе я закончил с несколькими вопросами, поэтому мы можем начать с них:
// 1. Write a program that takes an array and returns every other item function everyOther(array) { ... your code here //(hint: perhaps look in to Array#filter) } // 2. Write a function that returns another function. This one is as freeform as you want it to be! function returnF(input) { ...your code here } // 3. Write a program that prints out the numbers 0 through x on the screen WITHOUT using loops! function printNumbers(x) { ...your code here //(hint: look into recursion) }
1.
Во-первых, я буду использовать Array#filter (о котором мы поговорим на следующей неделе), чтобы вернуть все остальные элементы. Поскольку наши массивы работают с индексом, начинающимся с нуля, мы можем с уверенностью сказать, что все остальные индексы должны быть нечетными. Следовательно, мы можем вернуть отфильтрованный массив с помощью оператора модуля (%). Это дает нам то, что осталось от деления двух чисел. Так:
let arr = [1,2,3,4,5,6,7,8] function everyOther(arr) { return arr.filter((item, i) => (i % 2 == 0)) } everyOther(arr) // returns [1,3,5,7]
Это вернет массив, содержащий только элементы, индекс которых при делении на 2 равен 0.
2.
Этот более открытый. Мы можем написать здесь любую функцию, которую захотим, если она возвращает другую функцию. Давайте напишем такой, который облагает налогом процент налога с продаж и вычисляет, сколько будет в сумме сумма для товара по цене X.
function totalWithTax(tax) { return function(total) { return `$${total += (tax * total)}` } } let salesTax = totalWithTax(0.08) salesTax(15.50) // returns "$16.74"
Мы поймем, почему это так эффективно, в будущем с каррированием.
3.
Здесь мы определенно могли бы использовать цикл for, чтобы очень просто решить этот пример.
function printNumbers(x) { for (let i = x; i >= 0; i--) { console.log(i) } }
Хотя это не очень функционально. Он создает еще одну переменную, которая не нужна. Теперь мы можем начать с небольшой рекурсии и изучить лучший, более функциональный способ решения этой проблемы!
Рекурсия.
Если вы выполните поиск по термину рекурсия, вы увидите, что ребята из Google немного посмеются.
По сути, мы рассматриваем здесь следующее: рекурсивная функция — это функция, которая достигает своей цели, вызывая себя снова и снова. Чтобы это работало, нам нужно 2 бита информации. Во-первых, нам нужен завершающий случай, который остановит выполнение функции при выполнении определенного условия (подумайте о второй части цикла for — i ‹ arr.length или аналогичной). Во-вторых, нам нужна любая логика, которую мы хотим, чтобы программа выполняла. Итак, возвращаясь к вопросу номер 3:
function printNumbers(n) { //terminating case --without it, the program would //exceed maximum stack size and break the browser if (n == 0) return 0 else console.log(n) return printNumbers(n-1) } printNumbers(10) // returns 10 9 8 7 6 5 4 3 2 1 0
Это наша основная рекурсивная функция. По своей сути, это всего лишь базовое условное предложение. Если n == 0
, функция вернет 0 и завершится. Если нет, он перейдет к нашему оператору else, где запишет число. После этого возвращаем ту же функцию. Так это выглядит так:
- печататьЧисло(10). 10 == 0? Нет. Напечатайте 10 и вернитесь…
- печататьЧисло(9). 9 == 0? Нет. Напечатайте 9 и вернитесь…
- printNumber(8)… и так далее до возврата…
- номер печати (0). 0 == 0? да. Верните 0 и прекратите работу.
Примечание: это работает только потому, что когда мы снова вызываем нашу функцию в нашем операторе else, мы немного меняем параметр с помощью n-1
. Без этого возник бы бесконечный цикл, который нарушил бы нашу программу и уничтожил бы мир, каким мы его знаем.
Вооружившись этими знаниями, теперь мы можем делать еще более крутые вещи! При достаточной умственной гимнастике вы можете заменить каждый цикл for в своей программе рекурсией, если хотите! Но помните, что иногда самое простое решение оказывается лучшим. Используйте по своему усмотрению.
Давайте попробуем сделать что-то, что может пригодиться вам в будущем, возможно, если вы ищете работу. Возможно, вы знакомы с тестом FizzBuzz. Предпосылка:
Получив число (n), если оно делится и на 3, и на 5, выведите слово «FizzBuzz». Если делится только на 3, выведите «Fizz» или на 5, выведите «Buzz». Если ничего из перечисленного выше, выведите n, считая до 0.
Мы могли бы сделать это с помощью цикла for, но это кажется хорошей практикой для достижения мастерства в рекурсии. Давайте начнем с цикла for и посмотрим, как рекурсивно воссоздать его.
function fizzbuzz(n) { for (let i = n; i > 0; i--) { if (i % 3 == 0 && i % 5 == 0) console.log('fizzbuzz') else if (i % 5 == 0) console.log('fizz') else if (i % 3 == 0) console.log('buzz') else console.log(i) } } fizzbuzz(30) // works correctly.
Глядя на это, мы видим, что у нас уже есть обе вещи, необходимые для нашего рекурсивного примера, хотя и с небольшим количеством лишнего (и дополнительным нежелательным состоянием). У нас есть завершающий случай, заключенный в цикл for i > 0
, и у нас есть логика того, что мы хотим, чтобы наша функция выполнила (в операторах if / else if / else
. Все, что нам действительно нужно сделать, это удалить состояние (переменная i
, которую мы имеем). Мы можем сделать это, возвратив функцию с измененным параметром.Мы будем медленно высасывать состояние из нашей функции вместо того, чтобы вводить новое.
function fizzbuzz(n) { //change our for loop to our terminating case if (n == 1) return 1 //change our i to n since we removed the i variable if (n % 3 == 0 && n % 5 == 0) console.log('fizzbuzz') else if (n % 5 == 0) console.log('fizz') else if (n % 3 == 0) console.log('buzz') else console.log(n) //return our function with an altered parameter return fizzbuzz(n - 1) }
Теперь поток нашей программы выглядит так:
- fizzbuzz вызывается с параметром n
- N = 1? Нет. Продолжайте.
- n делится на 3 и 5? Если да, выведите и верните функцию с измененным параметром. Если нет, продолжайте.
- печатает соответствующее заявление.
- начинается с fizzbuzz (n-1) до тех пор, пока n = 1 и наша программа не завершится.
Вот оно! Надеюсь, этот пост поможет осмыслить рекурсивное функционирование. Их определенно сложно уложить в голове, но как только вы поймете концепцию, это станет чрезвычайно ценным инструментом для вашего комплекта программирования.
Вы можете связаться со мной в твиттере @spacebrayn или в комментариях ниже с вопросами, ответами, шутками папы или анекдотами. Мы вернемся к разговору о Map/Filter/Reduce на следующей неделе и начнем по-настоящему веселиться :) ttfn ❤